[数据结构与算法]1346：【例4-7】亲戚(relation)

• 开始学并查集！
• 白书的解释真的是……长且无用
• 总结：每个集合就是一棵树，以根节点判断是否在同一集合，合并集合就把一棵树的根节点连到另一棵树的根节点上。
• 除此以外，为防止出现链式结构降低搜索效率，可压缩路径，方法为递归回来是把路上的父亲节点全部连到根节点，能有效的降低复杂度。
• 传送门
• 模板题，注意数据较大，用scanf和printf.

#include<bits/stdc++.h>
using namespace std;
#define maxn 20010
int father[maxn];
int m,n,q;
int find(int x){
	if(father[x]!=x) father[x]=find(father[x]);
	//路径压缩，递归回来时把一路上的父亲节点都指到根节点，很巧妙 
	return father[x];
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		father[i]=i;
	int x,y;
	for(int i=1;i<=m;i++){
		int r1,r2;
		scanf("%d%d",&x,&y);
		r1=find(x),r2=find(y);
		if(r1!=r2) father[r2]=r1;//连接两棵树 
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		scanf("%d%d",&x,&y);
		if(find(x)==find(y)) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
} 

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖