并查集

发表于 更新于 分类于 ，

模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
int n,m,k,x,y;
int pre[200005];

int find(int x)
   //查找根
{
    if (x!=pre[x]) pre[x]=find(pre[x]);
    return pre[x];
}

void merge(int a,int b)
   //合并
{
    int x=find(a);
    int y=find(b);
    pre[x]=y;
}

int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        pre[i]=i;
    for (int i=1;i<=m;i++)
    {
        cin>>k>>x>>y;
        if (k==1) merge(x,y);
        if (k==2) 
        {
            int x0=find(x);
            int y0=find(y);
            if (x0==y0) cout<<"Y"<<endl;
            else cout<<"N"<<endl;
        }
    }
    return 0;
}

解释

并查集是可以快速完成判断两个元素是否在同一集合或者合并两个集合的一种数据结构。

将每一个元素都视为树上的一个节点，每一个集合就是一棵独立的树，指定一个集合中的任意一个元素为根，将其他元素以树的形式连接到这个根上。同时树中的每一个节点都存储着一个指针指向他的父节点。而根节点的父节点指向自己。

并查集有两种基础操作，查找根和合并集合。

查找一个元素的根时，因为每一个元素就是树上的一个节点，而节点记录着自己的父节点，所以可以利用递归顺着记录的父节点不断向上查找，直到找到一个节点其父节点就是他自己，这个节点就是根。

1
2
3
4
5
int find(int x)   //查找根
{
    if (x!=pre[x]) return find(pre[x]);
    else return x;
}

而合并两个集合时，也就是需要将其中一个集合的树连接到到另一个集合的树上，于是查找到其中一个树的根，并将这个根的父节点指向另一个树上的任意元素。

也就是说，合并集合是在查找根的基础上完成的。而查找根时，递归的深度是由当前节点到树根的距离决定的，而并不关系途中经过了哪些节点，即节点距离树根越近，递归深度越低。那么将每一个节点都直接连接在树根上，这是查找树根的速度将是最快的。于是在进行合并操作时，会同时找到要合并的两棵树的根，并将其中的一个根的父节点直接指向另一个根。

1
2
3
4
5
6
7
void merge(int a,int b)
   //合并
{
    int x=find(a);
    int y=find(b);
    pre[x]=y;
}

但这样做并不是最快的，还可以通过路径压缩使得操作更快一点。在利用递归查找根的同时，当找到根后，根的下标会被一路以返回给上一层函数，即查找过程中经过的子节点，这是就可以将途经的所有节点的父节点都指向根，也就可以使得更多的元素直接连接在根上，这样就完成了对树的压缩。

1
2
3
4
5
6
int find(int x)
   //查找根
{
    if (x!=pre[x]) pre[x]=find(pre[x]);
    return pre[x];
}

所以如果想要判断两个元素是否属于同一集合时，只需要分别查找这两个元素所在树的根，判断根是否一致即可。如果处于不同集合，则根不同。

1
2
3
4
int x0=find(x);
int y0=find(y);
if (x0==y0) cout<<"Y"<<endl;
else cout<<"N"<<endl;