并查集算法实现社区部落统计和关系查询

该程序使用并查集的思想来统计互不相交的部落以及检查两个人是否属于同一个部落。

首先，定义了一个大小为10010的'father'数组，用来保存每个人的父节点。初始化时，将每个人的父节点设为自己。

然后，通过输入读取小圈子的信息。对于每个小圈子，先读取小圈子的人数'k'和第一个人的编号'first'。将第一个人的编号加入到'total'集合中，并将第一个人的编号与后面的人的编号通过'uniont'函数进行合并。若'k'为1，则说明该小圈子只有一个人，不需要进行合并操作。

接下来，遍历'total'集合，将每个人的父节点加入到'cnt'集合中，用于统计互不相交的部落数量。

然后，输出'total'集合的大小（即社区中的人数）和'cnt'集合的大小（即互不相交的部落数量）。

最后，通过输入读取查询次数'm'，然后依次读取每对被查询的人的编号'a'和'b'。通过'find'函数判断'a'和'b'是否属于同一个部落，若属于同一个部落，则输出'Y'，否则输出'N'。

该程序没有使用文件操作或数据库操作。

程序代码：

#include<bits/stdc++.h>
using namespace std;
int father[10010];
int find(int x){
	while(x!=father[x])
		x=father[x];
	return x;
}
void uniont(int a,int b){
	int fa=find(a),fb=find(b);
	if(fa<fb)
		father[fb]=fa;
	else
		father[fa]=fb;
}
int main(){
	set<int>total;
	for(int i=0;i<10010;i++)
		father[i]=i;
	int n,k,num,first;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>k>>first;
		total.insert(first);
		if(k==1)
			continue;
		else{
			for(int j=1;j<k;j++){
				cin>>num;
				total.insert(num);
				uniont(first,num);	
			}
		}
	}
	set<int>cnt;
	for(auto i=total.begin();i!=total.end();i++)
		cnt.insert(find(*i));
	cout<<total.size()<<' '<<cnt.size()<<endl;
	int m,a,b;
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>a>>b;
		if(find(a)!=find(b))
			cout<<'N'<<endl;
		else
			cout<<'Y'<<endl;
	}
}