并查集（标准并查集、带权并查集、扩展域并查集）

什么是并查集？

并查集是一种数据结构，用来管理集合之间的关系，可以用来进行判断是否属于同一集合或将不同的集合合并等操作。

我们用个生活中的例子来说明一下

原本小明家这个集合只有小明，小红家只有小红，那么他们结婚后（合并）就属于一个家庭（一个集合），像这样，通过并查集我们能够合并不同的集合，然后还能快速地查找他们是不是同一个集合。

并查集的基本操作

合并集合的操作（将两个不同的集合合并）

这是两个不同的集合，我们想将两个集合合并的话，那么当然就是把2和4（接下来我们叫祖宗节点，一个集合一定只有一个祖宗节点，且祖宗节点的父节点等于它本身，因为祖宗节点往上没有节点了）连接起来就形成了一个集合。

查找祖宗节点（用于判断是否属于统一集合）

根据上图，我们要想找3的祖宗节点，就要递归找3这个节点的父节点的祖宗节点，一直递归，直到找到祖宗节点，如果每次都这样查找，每次查找的时间是O(logn)也就是高度次，看起来时间并不长，如果需要大量查找的话，就会大大降低效率，所以要引出路径压缩的操作，该如何操作呢？

我们希望：在第一次查询的时候，让路径上的每个节点都与祖宗节点相连，那么虽然在第一次查询的次数为高度
次，但下一次再次查询的时候，时间复杂度就会压缩成O(1).
1
2

下面用一道模板题来实现一下并查集的操作

#include<iostream>
using namespace std;
const int N=1e5+10;
int p[N];//记录该节点的父亲节点
int find(int x){
	//查找祖宗节点操作
	if(p[x]!=x){
	//如果该节点的父亲节点不是本身，说明不是祖宗节点
	p[x]=find(p[x]);//让父节点指向最终找到的父亲节点，递归
	}
	return p[x];//如果不是父节点等于本身，说明是祖宗节点，返回
}
int main(){
	int n,m;//n是数字个数，m是操作次数
	for(int i=1;i<=n;i++) p[i]=i;
	//一定要记得初始化，这样初始化的原因是因为一开始并没有集合合并
	//每个节点的父节点都是自己，也就是是说大家都是祖宗节点，都是不同的集合
	while(m--){
	char op[2];int a,b;
	scanf("%s%d%d",op,&a,&b);
	if(*op=='M'){
	p[find(a)]=find(b);//这个操作是指，a的祖宗节点的父节点是b的祖宗节点，目的就是让两个集合连接
	}
	else{
	if(find(a)==find(b)) puts("Yes");
	else puts("No");
	}
	}
	return 0;
}
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

以上是标准并查集的一些基本操作，接下来来介绍两个标准并查集的变种：带权并查集和扩展域并查集。并用一道经典例题来介绍这两种并查集的使用。
例题如下：

带权并查集

带权并查集是指在标准并查集的基础上，加上对权重（树的高度，数字大小）进行考虑和维护。
这道题为什么可以用带权并查集来解决呢？
首先先理解题意，A吃B，B吃C，C吃A。那么根据这个条件，如果我们知道了1吃2，2吃3，那么就可以知道一个隐含条件3吃1，因为他们是环形的。

上面我们知道，维护集合的关系使用并查集来处理，我们希望维护一些性质，能使得动物之间的关系能够查找到，这时候就要维护每个节点到祖宗节点的距离。（比较抽象，咱们来画个图理解）

我们先来看1和2的关系（注意这里的箭头指向，这里箭头指向的是猎物，没被指向的是食物，这里指1吃2）1到祖宗节点的距离为0，2到祖宗节点的距离为1，他们到根节点的距离相减mod3为1，那他和根节点（1）是食物关系（1吃2），3到祖宗节点的距离为2，1到祖宗节点的距离为0，他们到根节点的距离相减mod3为2，那他和根节点（1）是天敌关系（3吃1）。
如果假设a到根距离和b到根距离相减mod3（为什么mod 3是因为对于某一类来说只有3种情况，一种是同类，一种是食物，一种是天敌）为1，那么就是根节点这类动物的食物，mod 3为2就是根节点的天敌，mod 3为0就是根节点的同类。（）
肯定有小伙伴会疑惑，为什么一定满足这个关系？因为我们就是要按照这样的规律合并集合，所以才有了这样的规律。所以我们要将所有涉及到的动物全都按照上面的关系合并到一个集合内，不理解的小伙伴继续看代码，多次理解一下。
核心代码：

int find(int x){
    if(p[x]!=x){
        //如果父亲节点不是祖宗节点
        int t=find(p[x]);//记录一下祖宗节点
        d[x]+=d[p[x]];//x节点到根节点的距离等于x到父亲节点的距离加上父亲节点到祖宗节点的距离
        p[x]=t;//直接接在祖宗节点上，父节点是祖宗节点，实现路径压缩
    }
    return p[x];
}
1
2
3
4
5
6
7
8
9

我们画个递归展开图来模拟一下（红色为归的状态)

围绕以下关系

//如果在集合里，说明前面我们已经按照关系合并集合，只需根据关系来判断是不是同类，
不是同类就是假话
            //关系1：该点到根距离%3==0 和根是同类 
            //关系2：该点到根距离%3==1 是根的食物
            //关系3：该点到根距离%3==2 是根的天敌
            //再判断余数的关系就能把判断两个动物之间的关系啦
            //（d[b]%3-d[a]%3==0）->(d[a]-d[b])%3==0说明a、b同类
            //（d[b]%3-d[a]==1）->(d[a]-d[b]+1)%3!=0说明b是a的食物
1
2
3
4
5
6
7
8

主要代码如下：

if(a>n||b>n) {
	//a或b有一个超过数字总数就是假话
            ans++;
            continue;
        }
        int pa=find(a),pb=find(b);//先记录根节点，操作这一步之后，会进行路径压缩的操作，同时更新x节点到根节点的距离
        if(op==1){
            if(pa==pb&&(d[b]-d[a])%3!=0){
                ans++;//记录假话
                continue;
            }
            else if (pa!=pb){
                //不在同一集合，前面的话没有两者之间的关系，不发生冲突，不是假话，按照op==1是同类的关系合并集合
                p[pa]=pb;//pa是a的祖宗节点，pa的父节点是pb，合并两个集合
                d[pa]=d[b]-d[a]; //(d[a]+d[pa]-d[b])%3==0,a和b是一类
                //d[pa]我的理解是一段假想出来的距离，加上这段距离后，就能让b和a符合同类的关系
            }
        }
        else{
            if(a==b){
                ans++;
                continue;
            }
            if(pa==pb&&(d[a]-d[b]+1)%3!=0){
                ans++;
            }
            else if(pa!=pb){
                p[pa]=pb;
                d[pa]=d[b]-1-d[a];//（d[a]+d[pa]-dp[b]+1）%3==0
            }
        }
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

全部代码如下：

#include<iostream>
using namespace std;
const int N=50010;
int p[N];//记录该节点的父亲节点
int d[N];//记录的是该节点离父亲节点的距离！！！，在路径压缩的时候会更新成根节点的距离
int find(int x){
    if(p[x]!=x){
        //如果父亲节点不是祖宗节点
        int t=find(p[x]);//记录一下祖宗节点
        d[x]+=d[p[x]];//x节点到根节点的距离等于x到父亲节点的距离加上父亲节点到祖宗节点的距离
        p[x]=t;//直接接在祖宗节点上，父节点是祖宗节点，实现路径压缩
    }
    return p[x];
}
int main(){
    int n,k,ans=0;
    cin >> n >> k;
    for(int i=1;i<=n;i++) p[i]=i;//一开始每个动物都是自己一类的，还不知道他们之间的关系，d[i]是全局数组，已经默认为0
    while(k--){
        int op,a,b;
        scanf("%d%d%d",&op,&a,&b);
        if(a>n||b>n) {
            ans++;
            continue;
        }
        int pa=find(a),pb=find(b);//先记录根节点，操作这一步之后，会进行路径压缩的操作，同时更新x节点到根节点的距离
        if(op==1){
            if(pa==pb&&(d[b]-d[a])%3!=0){
                ans++;//记录假话
                continue;
            }
            else if (pa!=pb){
                //不在同一集合，前面的话没有两者之间的关系，不发生冲突，不是假话，按照op==1是同类的关系合并集合
                p[pa]=pb;//pa是a的祖宗节点，pa的父节点是pb，合并两个集合
                d[pa]=d[b]-d[a]; //(d[a]+d[pa]-d[b])%3==0,a和b是一类
            }
        }
        else{
            if(a==b){
                ans++;
                continue;
            }
            if(pa==pb&&(d[a]-d[b]+1)%3!=0){
                ans++;
            }
            else if(pa!=pb){
                p[pa]=pb;
                d[pa]=d[b]-1-d[a];
            }
        }
        
    }
    cout << ans;
    return 0;
}
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
45
46
47
48
49
50
51
52
53
54
55

个人认为带权并查集的做法是有一点难以理解，如果不理解的话，我们可以学习下面一种做法：
扩展域并查集

扩展域并查集

我们此时不能在再将x看作是某个动物，我们将x看作一个域
x，我们认为这个是x的同类域
x+n，我们认为这个是x的食物域
x+n+n，我们认为这个是x的天敌域

当我们讨论x与y的关系时
判断x与y是否同类
只需判断，y的食物域是否有x或着x的食物域是否有y，若都不满足
则x，y合并为一类，那么x的食物域和y的食物域也是一类，x的天敌域和y的天敌域也是一类，将它们合并

判断x是否吃y
这里就稍稍复杂些
只需判断x是否与y为同类或者y的食物域是否有x，若都不满足
则将x的食物域和y合并，x的天敌域和y的食物域合并，x和y的天敌域合并

代码如下：
核心的查找祖宗节点和合并集合操作仍没有改变

#include<iostream>
using namespace std;
const int N=150010;
int p[N];
int find(int x){
    if(p[x]!=x){
        p[x]=find(p[x]);
    }  
    return p[x];
}
void merge(int x,int y){
    p[find(x)]=find(y);
}
int main(){
    int n,k,ans=0;
    cin >> n >> k;
    for(int i=1;i<=3*n;i++) p[i]=i;
    
    while(k--){
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(x>n||y>n){ans++;continue;}
        if(op==1){
            if(find(x+n)==find(y)||find(x)==find(y+n)) {ans++;continue;}
            
                merge(x,y);
                merge(x+n,y+n);
                merge(x+n+n,y+n+n);
        }
        else{
            if(x==y||find(x)==find(y+n)||find(x)==find(y)){ans++;continue;}
            
                merge(x+n,y);
                merge(x+n+n,y+n);
                merge(x,y+n+n);
            
        }
        
    }
    cout << ans <<endl;
    return 0;
}
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

以上是本人对并查集的理解，如有错误，请指出，我会及时改正！感谢大家的观看！创作不易，如有收获，麻烦请您点个赞吧！你们的支持，是我继续创作的动力！感谢！