The Suspects并查集

The Suspects
原题链接https://vjudge.net/contest/350427#problem/B


大意就是有很多小组属于同一集合，判断跟0连在一起的有多少个，用sum记录每个根上有多少个数据，最后判断0的根上有多少数据即可。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<fstream>
#include<queue>
using namespace std;
long long vis[30005];
long long pre[30005];
long long sum[30005];
long long find(long long x)//搜索根，压缩路径
{
	if(x==pre[x])
	{
		return x;
	}
	return pre[x]=find(pre[x]);
}
void join(long long x,long long y)//链接
{
	long long ss1=find(x);
	long long ss2=find(y);
	if(ss1!=ss2)
	{
		pre[ss2]=ss1;
		sum[ss1]+=sum[ss2];//将两个集合的数合并到根上
	}
}
int main()
{
	long long i,n,m;
	while(~scanf("%lld %lld",&n,&m))
	{
		if(n==0&&m==0)
		{
			break;
		}
		for(i=0;i<=n;i++)
		{
			pre[i]=i;
			sum[i]=1;
		}
		long long i,j;
		while(m--)
		{
			long long sum,sum1,sum2;
			scanf("%lld",&sum);//sum为组员的数量
			scanf("%lld",&sum1);//第一个数
			sum--;
			while(sum--)//2-sum
			{
				scanf("%lld",&sum2);
				join(sum1,sum2);
			}
		}
	//	for(i=0;i<n;i++)
	//	{
	//		if(pre[i]==0)
	//		{
	//			printf("lainjie%lld ",i);
	//		}
	//	}
	//	printf("nn");
		printf("%lldn",sum[find(0)]);//找到0的根，根的集合的总数就是与0 链接的总数
	}
	return 0;
}

最后

以上就是爱听歌柜子为你收集整理的The Suspects并查集的全部内容，希望文章能够帮你解决The Suspects并查集所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。