5.并查集

并查集结构能够支持快速进行如下的操作：

  1. 将两个集合合并
  2. 询问两个元素是否在一个集合当中

并查集可以在近乎O(1)的时间复杂度下，完成上述2个操作

并查集的基本原理：用树的形式来维护一个集合。用树的根节点来代表这个集合。对于树中的每个节点，都用一个数组存储其父节点的编号。比如一个节点编号为x，我们用p[x]来表示其父节点的编号。当我们想求某一个节点所属的集合时，找到其父节点，并一直往上找，直到找到根节点

1.如何才能判断根结点？

当父节点为其本身时，此结点即为根节点：p[x]=x

2.如何求某结点x的集合编号？

从当前结点的父节点不断向上遍历，直到找到根节点，即为集合编号:while(p[x]!=x) x=p[x];

3.如何合并两个集合？

令某个集合的根节点为另一个集合根节点的父节点

优化：

未优化前查找某个元素的所属集合（也即查找两个元素是否在一个集合）的时间复杂度为O(logn)即树的高度，为使时间复杂度接近O(1)，采用路径压缩的方法优化，即每次查找元素所属集合的过程中，顺便使每个结点的父节点都指向根节点（即集合编号结点）

查询根节点（即所属集合编号）：find(x)

合并两个集合：p[find(a)]=find(b);

判断两个元素是否在同一个集合：find(a)==find(b)

AcWing 836.合并集合

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
#include <iostream>
using namespace std;

const int N=1e6+10;
int p[N];//父节点数组
int n,m;

//查找某个元素所属集合编号
int find(int x){
    if(p[x]!=x) return p[x]=find(p[x]);//递归查找 同时令每个结点的父结点都指向根节点
    return p[x];
}

int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;//初始化各个元素为一个集合
    while(m--)
    {
        char o[2];
        int x,y;
        cin>>o>>x>>y;
        if(o[0]=='M')
        {
            p[find(x)]=find(y);
        }
        else
        {
            if(find(x)==find(y)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}


AcWing 837.连通块中点的数量

实现思路：一个连通块视为一个集合，相比朴素并查集，就是多了一些维护信息

  • 在a和b之间连一条边，即合并集合，若同属一个集合就无需操作
  • 询问a和b是否在同一个连通块，即询问a和b是否在同一个集合
  • 询问a所在连通块的数量，即每次合并需额外维护一个数组记录集合中的元素个数（只有根节点的记录有意义）
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
40
41
42
43
44
#include <iostream>
using namespace std;

const int N=1e6+10;
int p[N];//父节点数组
int n,m;
int size[N];//记录对应集合中元素个数 只有集合根节点对应记录有意义

//查找某个元素所属集合编号
int find(int x){
    if(p[x]!=x) return p[x]=find(p[x]);//递归查找 同时令每个结点的父结点都指向根节点
    return p[x];
}

int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        p[i]=i;//初始化各个元素为一个集合
    	size[i]=1;
    }
    while(m--)
    {
        char o[5];
        int x,y;
        cin>>o>>x>>y;
        if(o[0]=='C')
        {
            if(find(x)==find(y)) continue;
            size[find(y)]+=size[find(x)];
            p[find(x)]=find(y);
        }
        else if(o[1]=='1')
        {
            if(find(x)==find(y)) puts("Yes");
            else puts("No");
        }else{
            cin>>x;
            cout<<size[find(x)]<<endl;
        }
    }
    return 0;
}


AcWing 240.食物链

实现思路：

  • 由题意可知任意两个动物可能存在三种关系之一：被吃，吃，同类。给定两个动物x和y，若知道这个两个动物与第三个动物z（中间人）的关系，则可推导出x和y的关系。如x吃y，y吃z，则可得z吃x，要形成一个环形食物链。

  • 考虑维护一个并查集，任意两个结点（动物）可能是三种关系之一，而只要存在一个中间人，知道这两个结点与中间人的关系就可以推断出这两个结点之间的关系。因此选择并查集的根结点（集合编号）为中间人，通过维护额外的信息来表示各结点与根节点的关系，就可以推断出集合中任意两个结点之间的关系。

    • 这个额外的信息选择当前结点到根节点的距离，因为存在三种关系，则用距离mod 3就可以得到三种结果，以此来表示当前结点与根节点的关系。
    • 设定mod 3=0表示当前结点与根节点是同类，mod 3=1表示吃根节点，mod 3=2表示被根节点吃。则mod 3=2的结点就吃mod 3=1的结点，mod 3值相同的结点是同类
    • 求每个结点到根节点的距离：在并查集的路径压缩过程中即设置每个结点的父节点为根节点时来完成。设置一个距离数组d[]，d[x]表示当前结点与父节点的距离。首先查找当前结点的根节点记录下来，然后该结点到根节点的距离=该结点到父节点的距离d[x]+父节点到根节点的距离d[p[x]]，再赋给d[x]，那么d[x]就更新成为当前结点到根节点的距离。最后更新x的父节点p[x]为根节点。

对一句话进行判断假话 还是真话

  • 若给出的x、y大于编号最大值n，直接判断为假话
  • 否则，继续判断。先得到x和y的根节点。再根据两种说法分别判断
    • 对第一种说法：x和y是同类。进行判断。若在同一个集合，用两者到根节点的距离对3取模判断，取模的值不相等就不是同类，为假话；否则为真话，就要先合并到同一个集合，然后更新x根结点到y根节点的距离使两者到根节点的距离满足x和y是同类。
      • 判断：d[x]%3!=d[y]%3====》(d[x]-d[y])%3!=0 假话
      • 更新距离（假设x合并到y的集合中）：(d[x]+d[p[x]])%3=d[y]%3=====》d[p[x]]=d[y]-d[x]
    • 对第二种说法：x吃y。若在同一个集合，判断x到根节点的距离mod 3是否满足比y到根节点的距离mod 3大1，若不满足，则x吃y是假话；否则真话，就要先合并到同一个集合，然后更新x父节点到根节点的距离，满足x吃y是真话。
      • 判断：d[x]%3-d[y]%3!=1====》(d[x]-d[y]-1)%3!=0 假话
      • 更新距离（假设x合并到y的集合中）：(d[x]+d[p[x]])%3-d[y]%3=1====》d[p[x]]=d[y]-d[x]+1

其他理解：

AcWing 240. 食物链—数组d的真正含义以及find()函数调用过程 - AcWing

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
40
41
42
43
44
#include <iostream>
using namespace std;
const int N=50010;
int p[N],d[N];//p表示父节点，d表示到父节点的距离 路径压缩后表示到根节点的距离
int n,m;

//得到根节点 并进行路径压缩更新d[x]为节点到根节点的距离
int find(int x){
    if(p[x]!=x){
        int t=find(p[x]);//得到根节点
        d[x]+=d[p[x]];//更新距离为到根节点的距离
        p[x]=t;//更新父节点为根节点
    }
    return p[x];
}
    
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    int res=0;
    while(m--){
        int q,x,y;
        cin>>q>>x>>y;
        if(x>n || y>n) res++;//假话
        else{
            int px=find(x),py=find(y);//得到各自根节点
            if(q==1){
                if(px==py && (d[x]-d[y])%3!=0) res++;//假话
            	else if(px!=py){//合并集合 更新距离
                	p[px]=py;
                	d[px]=d[y]-d[x];//满足x和y是同类
            	}
            }else{
                if(px==py && (d[x]-d[y]-1)%3!=0) res++;//假话
                else if(px!=py){//合并集合 更新距离
                    p[px]=py;
                    d[px]=d[y]-d[x]+1;//满足x吃y
                }
            }
        }
    }
    cout<<res;
    return 0;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。