题解：P10942 GF和猫咪的玩具

ycy1124 · 2024-09-27 16:22:37 · 题解

题意

本题最大的难点（？

有一个 n 个点，m 条长度为 1 的边的无向图，求图中任意两点间的最短距离的最大值。

分析

边权都一样，且无向，n 还那么小，直接暴力 bfs 就行了。

代码

#include<bits/stdc++.h>
#define qwq for(int i=1;i<=n;i++){bj[i]=0;}
struct Node{
    int p,w;
};
using namespace std;
int ans=0;
bool bj[101];
vector<int>a[101];
queue<Node>q;
void bfs(int p,int w){
    ans=max(ans,w);//更新答案
    bj[p]=1;
    for(auto it:a[p]){
        if(!bj[it]){
            q.push({it,w+1});
            bj[it]=1;
        }
    }
}
signed main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        a[u].push_back(v);
        a[v].push_back(u);//存无向图
    }
    for(int i=1;i<=n;i++){
        q.push({i,0});
        while(!q.empty()){
            bfs(q.front().p,q.front().w);//bfs
            q.pop();
        }
        qwq;//记得清空标记数组
    }
    printf("%d",ans);
    return 0;
}

AC 记录。