并查集基础与简单扩展应用

本文主要是介绍并查集基础与简单扩展应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

并查集的结构是一棵树

并查集有两种功能，一种是判断两个元素是否在同一集合，第二种是合并两个集合

并查集的实现需要记录每个节点的父亲节点

判断两个元素是否在同一集合，即判断两个元素的祖宗节点是否是一个节点（祖宗代表整棵树的根节点）

合并两个集合，即将任意一个集合祖宗的爸爸改为另一个集合的祖宗

---

基础题目

一共有 $n$ 个数，编号是 $1\sim n$，最开始每个数各自在一个集合中。

现在要进行 $m$ 个操作，操作共有两种：

1. M a b，将编号为 $a$ 和 $b$ 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
2. Q a b，询问编号为 $a$ 和 $b$ 的两个数是否在同一个集合中；

输入格式

第一行输入整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b，都要输出一个结果，如果 $a$ 和 $b$ 在同一集合内，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

$1\le n,m\le 10^5$

输入样例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例：

Yes
No
Yes

路径压缩

路径压缩的意思是将一个集合当中的除了 根节点的节点的父节点全部指向根节点，**这样做的目的是大大降低了每次找祖宗的时间

如下图所示

并查集需要提供一个 函数用于 查找每个元素的祖宗，路径压缩可以在该函数中实现

数组p记录的是该下标元素的父亲

在刚开始，每个编号自己是一个集合，它们的父亲是他们自己

#include <iostream>
using namespace std;const int N = 1e5+10;int p[N];
int n, m;//找到元素x 的祖宗
int find(int x)
{//如果x自己不是祖宗，则它的爸爸等于它爸爸的爸爸...if (p[x] != x) 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 op[3];int a, b;scanf("%s%d%d", op, &a, &b);//先获取祖先，避免重复进入函数浪费时间int pa = find(a), pb = find(b);if (op[0] == 'M'){if (pa != pb) //祖先不同{p[pa] = pb;//a的祖先的父亲是b的祖先}}else if (op[0] == 'Q'){//祖先不同则不在一个集合当中if (pa != pb) printf("No\n");else printf("Yes\n");}}return 0;
}

扩展应用

在使用并查集时，可以在原有基础上维护一些额外的东西

扩展题目1

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

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

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

输入格式

第一行输入整数 $n$ 和 $m$。

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

输出格式

对于每个询问指令 Q1 a b，如果 $a$ 和 $b$ 在同一个连通块中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点 $a$ 所在连通块中点的数量

每个结果占一行。

数据范围

$1\le n,m\le 10^5$

输入样例：

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例：

Yes
2
3

该题目需要维护一个整个集合当中元素的数量，需要额外创建一个数组来存储

不妨创建一个sz数组，每个集合的根节点，也就是所有点的祖宗，对应的值为整个集合节点的数量

扩展题目2

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

$A$ 吃 $B$，$B$ 吃 $C$，$C$ 吃 $A$。

现有 $N$ 个动物，以 $1\sim N$ 编号。

每个动物都是 $A,B,C$ 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 $N$ 个动物所构成的食物链关系进行描述：

第一种说法是 1 X Y，表示 $X$ 和 $Y$ 是同类。

第二种说法是 2 X Y，表示 $X$ 吃 $Y$。

此人对 $N$ 个动物，用上述两种说法，一句接一句地说出 $K$ 句话，这 $K$ 句话有的是真的，有的是假的。

当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1. 当前的话与前面的某些真的话冲突，就是假话；
2. 当前的话中 $X$ 或 $Y$ 比 $N$ 大，就是假话；
3. 当前的话表示 $X$ 吃 $X$，就是假话。

你的任务是根据给定的 $N$ 和 $K$ 句话，输出假话的总数。

输入格式

第一行是两个整数 $N$ 和 $K$，以一个空格分隔。

以下 $K$ 行每行是三个正整数 $D，X，Y$，两数之间用一个空格隔开，其中 $D$ 表示说法的种类。

若 $D=1$，则表示 $X$ 和 $Y$ 是同类。

若 $D=2$，则表示 $X$ 吃 $Y$。

输出格式

只有一个整数，表示假话的数目。

数据范围

$1\le N\le 50000$,
$0\le K\le 100000$

输入样例：

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

输出样例：

3

思路：我们需要额外维护一个每个节点到父节点的距离，路径压缩后也就是到根节点的距离

无论是什么动物，一旦说了它与另一个动物的关系，都统统放在一个集合里面

在集合当中，每个动物之间的关系由它们的距离所决定

在没有路径压缩前（如上图），每个边的距离都是1，我们可以规定 儿子吃父亲，所以2、3、4号点吃1号点，5号点吃2号点，7号点和1号点是同类，因为只有三种动物

虽然进行了路径压缩，但是可以通过每个节点到根节点的距离判断两个动物的关系

---

准备阶段：

需要多开辟一个数组存储距离

接下来是核心重点，需要对并查集当中的 find函数进行修改，需要在路径压缩的时候将数组d当中的距离从到父节点的距离该为到根节点的距离

如果超出节点范围就一定是假话

---

---

d[px] = d[y] - d[x];语句的原因如下：

由于我们写的是 p[px] = py，也就是让px的父亲是py，那么py就是整个合并后集合的根节点

由于需要满足x 和 y 是同类，所以 x到py这个新根节点的距离需要和y到py的距离满足 相等的关系即可。

所以 d[x] + d[px] = d[y]，d[px] = d[y] - d[x]

---

接下来是 x 吃 y的情况

写成(d[x] - d[y] - 1） % 3 != 0 而不是 (d[x] - d[y]) % 3 != 1 是因为

(d[x] - d[y] - 1) % 3 != 0包含了两种情况，先看下图

当 x 到根节点的 距离大于 y 到根节点的距离时，此时满足 x 吃 y 的情况

(d[x] - d[y] - 1) % 3 等于 0，(d[x] - d[y]) % 3 等于 1

当 x 到根节点的距离小于 y 到根节点的距离时，此时 也满足 x 吃 y 的情况

(d[x] - d[y] - 1) % 3 等于 0，(d[x] - d[y]) % 3 等于 -2，所以两种情况下都是等于0的，只需要写一种，而如果是写成 (d[x] - d[y]) % 3 != 1就需要在加上
(d[x] - d[y]) % 3 != -2 才可以.

---

d[px] = d[y] + 1 - d[x]的原因如下图所示

x 吃 y，所以我们设置距离的时候要么 x 的距离（到py根节点的距离）比 y 的长1,要么短2，这里就选择 长1

所以 d[px] 等于 d[y] + 1 - d[x]；

---

最终打印 假话 的数量即可

#include <iostream>using namespace std;const int N = 50010;int p[N], d[N];//存储到父节点的距离，
int n, m;      //由于进行了路径压缩所以也是到根节点的距离int find(int x)
{if (p[x] != x)//如果x不是祖先节点（根节点） {int t = find(p[x]);//先把祖先存起来，因为要用x的爸爸d[x] += d[p[x]];//x到父距离 加上 x的爸爸到爷爷的距离p[x] = t;//x的爸爸变成刚才存的祖先}return p[x];//返回x的祖先
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) p[i] = i;//最初的时候每个元素自成一个集合，所以到父节点（或根节点）的距离为0//因为全局变量的数组默认是0，所以不用初始化int res = 0;//假话的数量while (m --)//m句话{int t, x, y;//这里的名字千万不能是d,否则会与数组d重名scanf("%d%d%d", &t, &x, &y);if (x > n || y > n) res++;//如果超出节点范围 就一定是假话else{int px = find(x), py = find(y);//先确定祖先if (t == 1)// 题目说x 和 y 是同类{if (px == py && (d[x] - d[y]) % 3) res++;//如果在一个集合说明这两个节点已经产生某种关系//如果是同类，则距离之差一定3的倍数else if (px != py)//不相等说明第一次提到两点的关系{//所以要把 x 和 y弄成同类动物//1.先合并集合p[px] = py;// x 的祖先的父亲是y的祖先d[px] = d[y] - d[x];}}else if (t == 2) //题目说 x 吃 y;{if (px == py && (d[x] - d[y] - 1) % 3) res++;//不可以写成(d[x] - d[y]) % 3 != 1else if (px != py){p[px] = py;d[px] = d[y] + 1 - d[x]; }}}}cout << res << endl;return 0;
}

这篇关于并查集基础与简单扩展应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---