自动搬运

查看原文

来自洛谷，原作者为

	ycy1124 ENTJ-A | 有事私。| 清关了，私信基本也不会回关（除非满足条件），但可以支持小号回关 | 出去玩去了。不在线。微信可能上。

搬运于2025-08-24 23:02:45，当前版本为作者最后更新于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 记录。