友谊纽带

NC220126. 友谊纽带

描述

小航是计算机系的学生，但他并不喜欢自己的专业。在课余时间，小航喜欢研究社会学的内容，在他经过了多年的研究后，他发现了一个伟大的定理：世界上任意两个人之间最少需要k个友谊纽带就可以全部连接。他需要向世界公布这个研究成果，但是他还没有对这个定理进行验证，由于他急着陪女朋友，所以将验证这个定理的任务交给了他的朋友小杰和小坤。

由于人数太多，而导致任务量非常大，所以小杰和小坤找到了你，请你帮助他们验证这个结论。

输入描述

第一行包含两个整数n和m，n为总共的人数，m为关系的对数。
接下来m行包含两个整数a和b，表示a和b是朋友关系。

输出描述

如果n个人当中的某些人无法成为朋友，则输出-1。否则输出一个k，表示最少需要k个纽带就可以连接任意两个朋友(每两个人之间最多有一条纽带)。

示例1

输入:

输出:

说明:

1号朋友和5号朋友需要最多4个纽带才能连接

示例2

输入:

输出:

-1

说明:

1号朋友和5号朋友无法通过友谊纽带连接

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 49ms, 内存消耗: 608K, 提交时间: 2021-04-16 17:06:35

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+10;
struct node
{
	int x,s;
}q[maxn];
bool vis[maxn];
vector <int> v[maxn];int n,m,mx;
void bfs(int s)
{
	int l=1,r=1;memset(vis,0,sizeof vis);
	q[l]=(node){s,0};vis[s]=1;
	int cnt=0;
	while(l<=r)
	{
		cnt++;
		for(int y:v[q[l].x])
		{
			if(vis[y])	continue;
			vis[y]=1;
			q[++r]=(node){y,q[l].s+1};
			mx=max(mx,q[r].s);
		}
		l++;
	}
	if(cnt!=n)
	{
		printf("-1\n");
		exit(0);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int t1,t2;
		scanf("%d%d",&t1,&t2);
		v[t1].push_back(t2);
		v[t2].push_back(t1);
	}
	for(int i=1;i<=n;i++) bfs(i);
	cout<<mx<<endl;
}