【基础算法】彻底搞懂并查集

1.什么是并查集

并查集是一种基于树的数据结构，它对集合能够高效地实现以下操作：

（1）合并两个不同的集合

（2）询问两个元素是否在同一个集合内

（3）维护额外的信息，如权值，结点到祖宗节点的距离，集合中点的数量等。

2.基本原理

每个集合用一棵树来表示，根节点的编号作为整个集合的编号，每个节点则存储其父节点的编号。

3.基本操作

设节点x，则父节点则为fa[x]，初始化时令所有x的父节点均为自己。

（1）判断树根：只有根节点的父节点是自己，因此只需要判断节点父节点是否等于本身，即

if(x == fa[x])
{
    //操作
}

（2）求节点所在树的根节点（即求该集合的编号）：父节点不是自己就把自己更新成爹再去找

if(x != fa[x])
{
    x = fa[x];
}

（3）合并两个集合：任意将其中一个集合的根节点赋值给另一个根节点的父节点即可完成合并操作

【合并前】

【合并后】

//x，y分别是两个集合的根节点
fa[x] = y;

4.优化：路径压缩法

每个节点在寻找根节点的过程，都可能要经历多次迭代更新才能找到根节点，当树的高度足够大时，寻找根节点的迭代过程的时间代价较高，因此我们可以用降低树的高度的方式间接减少时间代价。

具体操作是，最终寻找到根节点后，将路径上所有节点直接与根节点相连，即搜索路径上的所有节点的父节点均直接全部变为根节点。

【迭代过程】

【完成优化】

5.核心代码实现

递归寻找根节点，找到后返回根节点并赋值给路径上所有节点作为父节点

//求某节点的根节点+路径压缩
int find(int x)
{
    if(x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}

6.例题1 集合的合并与查询

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

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

接下来 M 行，每行包含三个整数 Z_i,X_i,Y_i 。

当 Z_i=1 时，将 X_i 与 Y_i 所在的集合合并。

当 Z_i=2 时，输出 X_i 与 Y_i 是否在同一集合内，是的输出 Y ；否则输出 N 。

输出格式

对于每一个 Z_i=2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

样例 #1

样例输入 #1

样例输出 #1

N
Y
N
Y

提示

对于 30% 的数据，N \le 10，M \le 20。

对于 70% 的数据，N \le 100，M \le 10^3。

对于 100% 的数据，1\le N \le 10^4，1\le M \le 2\times 10^5，1 \le X_i, Y_i \le N，Z_i \in { 1, 2 }。

思路分析：简单合并和查询操作，不细说。

C++代码:

#include<iostream>
using namespace std;

const int N = 1e4 + 10;

int n, m, fa[N];

int find(int x)
{
    if(x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}

int main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++) fa[i] = i;
    
    while(m --)
    {
        int z, x, y;
        cin >> z >> x >> y;
        
        if(z == 1) fa[find(x)] = find(y);
        else
        {
            if(find(x) == find(y)) puts("Y");
            else puts("N");
        }
    }
    
    return 0;
}

7.例题2 连通块中点的数量

题目描述

给定一个包含 nn 个点（编号为 1∼n1∼n）的无向图，初始时图中没有边。

现在要进行 mm 个操作，操作共有三种：

C a b，在点 aa 和点 bb 之间连一条边，aa 和 bb 可能相等；
Q1 a b，询问点 aa 和点 bb 是否在同一个连通块中，aa 和 bb 可能相等；
Q2 a，询问点 aa 所在连通块中点的数量；

输入格式

第一行输入整数 nn 和 mm。

接下来 mm 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。 Y ；否则输出 N 。

输出格式

第一行输入整数 nn 和 mm。

接下来 mm 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

样例 #1

样例输入 #1

样例输出 #1

Yes
2
3

数据范围

1 ≤ n,m ≤ 105

思路分析：设s[N]，给每个节点设置节点总数，但只有根节点的节点总数是有意义的，合并时更新根节点的节点总数即可。

C++代码：

#include<iostream>
using namespace std;

const int N = 1e5 + 10;

int fa[N], s[N], n, m;

int find(int x)
{
    if(x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}

int main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++)
    {
        fa[i] = i;
        s[i] = 1;
    }
    
    while(m --)
    {
        string op;
        cin >> op;
        if(op == "C")
        {
            int x, y;
            cin >> x >> y;
            if(find(x) != find(y)) s[find(y)] += s[find(x)];
            fa[find(x)] = find(y);
        }
        else if(op == "Q1")
        {
            int x, y;
            cin >> x >> y;
            if(find(x) == find(y)) puts("Yes");
            else puts("No");
        }
        else
        {
            int x;
            cin >> x;
            cout << s[find(x)] << endl;
        }
    }
    
    return 0;
}

8.实战1 朋友圈

（来源：集美大学第十三届蓝桥校选拔赛第三题）

题目描述

某学校有n个学生，形成m个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好，形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出，如果A和B是朋友，且B和C是朋友，则A和C也是朋友。

现在学校有重要消息要通知，把消息通知给某个人需要花费代价c，但朋友之间传递是不需要代价的，可以看成花费代价为0，并且当某个人知道这个消息后，就会把消息立即告诉他的朋友。

请你计算把这个消息通知给所有人需要至少花费多少代价。

输入格式

第一行，包含两个整数n，m

第二行，包含n个整数，依次为c1,c2,....,c**n，表示通知消息给某个人所需要的花费

后面的m行每行按以下格式给出1个俱乐部的信息，其中学生从1−n编号：

第i个俱乐部的人数mi（空格）学生1（空格）学生2…学生mi

输出格式

输出一个整数，表示把消息通知给所有人至少花费多少代价

样例 #1

样例输入 #1

7 4
2 3 4 5 6 7 4
3 1 2 3
2 1 4
3 5 6 7
1 6

样例输出 #1

数据范围

对于50%的测试点，1≤n≤1000，1≤m≤30，1≤c**i≤1000

对于100%的测试点，1≤n≤30000，1≤m≤1000，1≤c**i≤1000

思路分析：将每个俱乐部输入的第一位同学作为根节点，再将该俱乐部的其他同学合并到同一集合，最后遍历所有集合即可。

C++代码：

#include<iostream>
#include<unordered_map>
using namespace std;

const int N = 30010;

int n, m, fa[N], c[N], ans[N];

int find(int x)
{
    if(fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

int main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++)
    {
        cin >> c[i];
        fa[i] = i;
    }
    
    while(m --)
    {
        int num, head;
        cin >> num >> head;
        for(int i=1; i<num; i++)
        {
            int stu;
            cin >> stu;
            fa[find(stu)] = find(head);
        }
    }
    
    int res = 0;
    
    for(int i=1; i<=n; i++)
    {
        int stu = find(i);
        if(ans[stu]) ans[stu] = min(ans[stu], c[i]);
        else ans[stu] = c[i];
    }
    
    for(int i=1; i<=n; i++) res += ans[i];
    
    cout << res << endl;
    
    return 0;
}

9.实战2 食物链

（来源：洛谷P2024[NOI2001]）

题目描述

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。

现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 N 个动物所构成的食物链关系进行描述：
- 第一种说法是 1 X Y，表示 X 和 Y 是同类。
- 第二种说法是2 X Y，表示 X 吃 Y 。
此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
- 当前的话与前面的某些真的话冲突，就是假话
- 当前的话中 X 或 Y 比 N 大，就是假话
- 当前的话表示 X 吃 X，就是假话
你的任务是根据给定的 N 和 K 句话，输出假话的总数。

输入格式

第一行两个整数，N，K，表示有 N 个动物，K 句话。

第二行开始每行一句话（按照题目要求，见样例）

输出格式

一行，一个整数，表示假话的总数。

样例 #1

样例输入 #1

样例输出 #1

数据范围

对于50%的测试点，1≤n≤1000，1≤m≤30，1≤c**i≤1000

对于100%的测试点，1≤n≤30000，1≤m≤1000，1≤c**i≤1000

思路分析：将所有动物存入并查集中，每个节点存放该节点到根节点的距离。假定A吃B，B吃C，C吃A，因此在并查集中，可以设，到根节点的距离余1的点吃根节点，到根节点的距离余2的点被根节点吃，而余0的则是根节点的同类，那么在并查集这棵树上，所有关系就显而易见了。

C++代码：

#include<iostream>
using namespace std;

const int N = 1e5 + 10;

int n, k, fa[N], d[N];

int find(int x)
{
    if(x != fa[x])
    {
        int t = find(fa[x]);
        d[x] += d[fa[x]];
        fa[x] = t;
    }
    return fa[x];
}

int main()
{
    cin >> n >> k;
    for(int i=1; i<=n; i++) fa[i] = i;
    
    int res = 0;
    while(k --)
    {
        int op, x, y;
        cin >> op >> x >> y;
        
        if(x > n || y > n) res ++;
        else
        {
            int fx = find(x), fy = find(y);
            
            if(op == 1)
            {
                if(fx == fy && (d[x] - d[y]) % 3) res ++;
                else if(fx != fy)
                {
                    fa[fx] = fy;
                    d[fx] = d[y] - d[x];
                }
            }
            
            else if(op == 2)
            {
                if(fx == fy && (d[x] - d[y] - 1) % 3) res ++;
                else if(fx != fy)
                {
                    fa[fx] = fy;
                    d[fx] = d[y] + 1 - d[x];
                }
            }
        }
    }
    
    cout << res << endl;
    return 0;
}

你学fei了吗？