萌新刚学并查集,求助各位大佬
查看原帖
萌新刚学并查集,求助各位大佬
719611
__2304__楼主2024/5/26 15:10
#include<iostream>
#include<string.h>
using namespace std;
const int MAXN=2e3+5;
int t,n,m,c[MAXN],e[MAXN][MAXN],s[MAXN],k;
void init_set(){
	for(int i=1;i<=n;i++) s[i]=i;
}
int find_set(int x)
{
	if(x==s[x]) return x;
	else return find_set(s[x]);
}
void union_set(int x,int y)
{
	x=find_set(x),y=find_set(y);
	if(x!=y) s[x]=s[y];
}
void bfs(int x)
{
	for(int i=1;i<=n;i++){
		if(x!=i&&e[x][i]==1){
			c[i]=3-c[x];
			bfs(i);
		}
	}
	return;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		k++;
		scanf("%d%d",&n,&m);
		init_set();
		int a,b;
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&a,&b);
			if(a<b) e[a][b]=1;
			else e[b][a]=1;
			union_set(b,a);
		}
		for(int i=1;i<=n;i++) if(i==s[i]){c[i]=1;bfs(i);}
		int f=0;
		for(int i=1;i<=n-1;i++) for(int j=i+1;j<=n;j++) if(e[i][j]&&(c[i]==c[j])) f=1;
		//cout<<"Scenario #"<<k<<":"<<endl;
		printf("Scenario #%d:\n",k); 
		if(f) printf("Suspicious bugs found!\n");
		else printf("No suspicious bugs found!\n");
		memset(e,0,sizeof(e));
		memset(c,0,sizeof(c));
	}
	return 0;
}
2024/5/26 15:10
加载中...