“你只看见我渺小的身躯，却没有看到我心中的广阔森林。”

---

基础知识

---

并查集常见的两个操作：

• 合并（Union）：把两个不相交的集合合并为一个集合。
• 查询（Find）：查询两个元素是否在同一个集合中。

并查集是一种用于处理一些不相交的集合的合并与查询问题的树形数据结构，能够将两个集合合并或者查询某个元素处于哪个集合中

---

模板题：洛谷P3367 【模板】并查集

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。

接下来 M 行，每行包含三个整数 Zi​ , Xi ​, Yi​ 。

当 Zi​=1 时，将 Xi​ 与 Yi​ 所在的集合合并。

当Zi​=2 时，输出 Xi​ 与 Yi​ 是否在同一集合内，是的输出 Y ；否则输出 N 。

输出格式

对于每一个 Zi​=2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

输入输出样例

输入 #1

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

输出 #1

N
Y
N
Y

说明/提示

对于 30% 的数据， N≤10，M≤20。

对于70% 的数据，N≤100，M≤10^3。

对于 100% 的数据，1≤N≤10^4， 1≤M≤2×10^5，1≤Xi​,Yi​≤N，Zi​∈{1,2}。

---

#include 
#include 
#include 
using namespace std;
int z,x,y,fa[100000];
int find(int x)  //查找根节点
{
	if(x==fa[x]) return x; //如果父节点已经是根节点，返回该值	
	else 
	{
		fa[x]=find(fa[x]); //将父节点设为根节点
		return fa[x]; //返回父节点
	}
}
 
/*现在常写：
int find(int x)  
{
	if(x==fa[x]) return x;	
	return fa[x]=find(fa[x]);
}
*/ 
 
void add(int x,int y) //将两个元素合并成一个集合
{
	fa[find(y)]=find(x); //将两者中的其中一个元素设为另一个元素的父节点
}
 
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		fa[i]=i; //集合初始化，最初的所有元素的父节点都是自己
	}
	for(int i=1;i<=m;++i)
	{
		scanf("%d %d %d",&z,&x,&y);
		if(z==1) add(x,y); //合并操作
		else
		{
			if(find(x) == find(y)) //比较根节点是否相同
			printf("Y\n");  //相同则在一个集合中
			else printf("N\n");
		}
	}
	return 0;
}

---

相关练习：1.洛谷P1536 村村通 

注意：当n==0时才能结束程序 

#include 
#include 
#include 
#include 
using namespace std;
const int maxn=1e7+5;
int fa[maxn];
inline int find(int x)
{
	if(x == fa[x]) return x;
	return fa[x] = find(fa[x]);
}
 
int main()
{
	int n,m,x,y;
	while(cin>>n&&n!=0)
	{
		int ans=0;
		scanf("%d",&m);
		for(int i=1;i<=n;++i)
		{
			fa[i]=i;
		}
		
		for(int i=1;i<=m;++i)
		{
			scanf("%d%d",&x,&y);
			int p=find(x);
			int q=find(y);
			if(p==q) continue;
			fa[q]=p;	
		}
 
		for(int i=1;i<=n;++i)
		{
			if(fa[i]==i) ans++; 
                //自己的父亲等于自己本身，找到某个根的相关节点
		}
		printf("%d\n",ans-1);
	}
	return 0;	
}