2325: 肺炎大作战

看到要将一堆人联系起来，本蒟蒻第一时间想到的就是并查集，但是这里要我们输出的是最大群体。我们知道并查集路径压缩后每次查找这个群体的时候都会返回他们的“”祖宗“”，所以我们将群体的大小保存在“”祖宗“”里面，这样当两个群体合并的时候只需要将“”祖宗“”里面的数加到另外一个群体的‘’祖宗‘’就好了

AC代码:

#include<bits/stdc++.h>
using namespace std;
int flag[100005];
int sum[100005];
int find(int x)
{
	if(x!=flag[x])
	{
		flag[x]=find(flag[x]);
	}
	return flag[x];
}
void marge(int x,int y)
{
	int a=find(x);//找祖宗
	int b=find(y);//找祖宗
	if(a!=b)
	{
		flag[b]=a;//y的祖宗认x的祖宗为祖宗
		sum[a]+=sum[b];//将y的祖宗的人数加到x的祖宗里面
	}
}
int main()
{
	int n;
	while(~(scanf("%d",&n)))
	{
		for(int i=1;i<=100000;i++)
		{
			flag[i]=i;//一开始祖宗就是自己
			sum[i]=1;//一开始每个人都是为1的群体
		}
		while(n--)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			marge(x,y);
		}
		int maxn=0;
		for(int i=1;i<100000;i++)//找最大的群体
		{
			maxn=max(maxn,sum[i]);
		}
		printf("%d\n",maxn);
	}
	return 0;
}