【数据结构】并查集1
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;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
