1.引入

    对于一个集合S={a1, a2, …, an-1, an}，我们还可以对集合S进一步划分: S1,S2,…,Sm-1,Sm，我们希望能够快速确定S中的两两元素是否属于S的同一子集。

    举个栗子，S={0，1, 2, 3, 4, 5, 6}，如果我们按照一定的规则对集合S进行划分,假设划分后为S1={1, 2, 4}, S2={3, 6}，S3={0, 5}，任意给定两个元素，我们如何确定它们是否属于同一子集？某些合并子集后，又如何确定两两关系？基于此类问题便出现了并查集这种数据结构。

2.概念

    并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。

并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。

3.作用

    并查集可以高效的对元素进行分组（合并在一起），并且能快速的查询两个元素是否属于同一组。

4.基本操作

    合并：合并两个集合。join函数

    查找：判断两个元素是否在一个集合。find函数 

5.过程解释

    假如有两个集合，之间的关系可以用下面的图像表示：

一开始，分成两组，1和2是同一组，1和3是同一组，那么有没有什么办法可以将这两组练习起来。我们将1视为2的父级，1可以视为3的父级

这样，我们可以把图片划分成下面这样：

那么如果我们有其他的数据，比如下面的4，5，6这样表示

那么新问题来了，这两个集合如果在一块应该怎么表示呢？很简单，让这两个集合中的‘老大’打一架，谁赢了，谁就是两个集合共同的‘老大’。

假如 编号1 赢了，那么集合应该变成下面这样：

也就1成了所有人的‘老大’

那么也就是形成了一个等级严格的树形结构。

从数据结构上看，我们关注的重点是两个数据之间是否连通。

那么看下面这个例子

对于上面这个图，我们如何界定两个节点之间是否有关系呢？比如下面这两个题：

(1)问：2和3之间是否存在关系？

(2)问：3和7之间是否存在关系？

对于问题(1)，我们从图中可以很明显的看出，2和3之间有关系，因为他们有共同的’老大‘。

对于问题(2),  我们从图中也可以明显的看出，3和7之间没有关系，因为从3开始往上找，发现老大是1，而从7开始找，我们发现老大是4，这两个老大（根节点）不一样，说明没有关系。

在做题中，也就是我们输入每组的对应关系如下，

1 2  1 3  4 5  4 6  6 7

然后询问任意两个数（节点）之间有没有关系?

6.代码实现

（1）初始化

我们用f数组表示父级元素节点，初始化代码如下

int f[100]; //父节点     //初始化 n个元素   void Init() {  	//使每个元素的根节点是其本身  	//即初始时每个元素都是单独的   	for(int i=1; i<=n; i++){  			f[i]=i;    	}   }

’每个节点都是自己的父节点‘

（2）查询操作

查询操作有两种实现方式，一种是递归实现，另一种是非递归实现。

递归实现：

int find(int x){      if(f[x] == x)          return x;      else          return find(f[x]);}

一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。

非递归实现：

int find(int x) {  	while(f[x] != x) {  //直到元素的父节点是它本身，表示已经查询到了树的根  		x= f[x];  	return x; 			//返回根节点对应的元素   }

（3）合并

void merge(int a, int b) {  	//先找到两个元素对应的根对应的元素   	int fa = find(a);   	int fb = find(b);  	if(fa==fb) return;  	else f[fa]=fb;  //否则令元素 a的根指向元素 b的根   }

合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者。

6.例题

【题目描述】

【输入描述】

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

接下来M行，每行3个整数z,x,y。

当z=1时，将x和y集合合并

当z=2时，判断x和y是否属于同一集合，如果是输出YES，否则输出NO

【输出描述】

对于每个z=2，判断输出YES或者NO

【样例输入】

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

【样例输出】

NO  YES  NO  YES

【参考代码】

#include<bits/stdc++.h>  using namespace std;  int n,m,f[10010];  int z,x,y;  int find(int x)//找出某棵树的老大   {  	if(f[x]==x)//x是x的老大，  		return x;  	else   		return find(f[x]);//x不是他自己的老大，所以他上面还有老大，递归   }  void merge(int x,int y)  {  	//先找到两个元素对应的根对应的元素   	int fx = find(x);   	int fy = find(y);  	if(fx==fy) return;  	else f[fy]=fx;  //否则令元素 x的根指向元素 y的根    	return ;  }  int main()  {  	cin>>n>>m;   	//初始化每个人   	for(int i=1;i<=n;i++)  		f[i]=i;    	//询问   	for(int i=1;i<=m;i++)  	{  		cin>>z>>x>>y;   		if(z==1){  			merge(x,y);  		}else{  			if(find(x)==find(y)){  				cout<<"YES"<<endl;  			}else{  				cout<<"NO"<<endl;  			}   		}  		  	}  	return 0;  }

(adsbygoogle = window.adsbygoogle || []).push({});