并查集
并查集
并查集
一、定义
并查集是一种树型的数据结构,用于处理一些不相交集合(disjoint sets)的合并及查询问题。
二、主要操作
- 初始化
把每个点所在集合初始化为其自身。
通常来说,这个步骤在每次使用该数据结构时只需要执行一次,无论何种实现方式,时间复杂度均为O(N)。 - 查找
查找元素所在的集合,即根节点。可用于询问两个元素是否在同一个集合中。 - 合并
将两个元素所在的集合合并为一个集合。
通常来说,合并之前,应先判断两个元素是否属于同一集合,这可用上面的“查找”操作实现。
三、实现
基本原理:每个集合用一棵树来表示。树根的编号就是整个集合的编号,每个结点存储它的父节点,f[x]表示x的父节点。
- 如何判断是否是根: if(f[x]==x)
- 如何求x的集合编号: while(f[x]!=x) x=f[x];
- 如何合并两个集合:f[x]=y;
如果只是这样的话,会发现在求x的集合编号时的速度仍然比较慢,因此需要一些优化。
优化1:路径压缩:
并查集在不断合并的过程中,可能会形成一条长长的链,随着链越来越长,我们想要从底部找到根节点会变得越来越难。怎么解决呢?我们可以使用路径压缩的方法。既然我们只关心一个元素对应的根节点,那我们希望每个元素到根节点的路径尽可能短,最好只需要一步。
只要我们在查询的过程中,把沿途的每个节点的父节点都设为根节点即可。下一次再查询时,我们就可以省很多事。这用递归的写法很容易实现:
1 | int find(int x) |
优化2:按秩合并:
现在我们有一棵较复杂的树需要与一个单元素的集合合并。我们应该把简单的树往复杂的树上合并,而不是相反。因为如果复杂的往简单的合并,会使树的深度(树中最长链的长度)加深,原来的树中每个元素到根节点的距离都变长了,之后我们寻找根节点的路径也就会相应变长。虽然我们有路径压缩,但路径压缩也是会消耗时间的。
我们用一个数组rank[]记录每个根节点对应的树的深度(如果不是根节点,其rank相当于以它作为根节点的子树的深度)。一开始,把所有元素的rank(秩)设为1。合并时比较两个根节点,把rank较小者往较大者上合并。路径压缩和按秩合并如果一起使用,时间复杂度接近 O(N),但是很可能会破坏rank的准确性。
按树深度合并代码实现:
1 | void merge(int i, int j) |
按树的结点数量合并:
1 | void merge(int i, int j) |
四、例题和完整模板
洛谷P1551 亲戚
题目背景
若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。
题目描述
规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。
输入格式
第一行:三个整数n,m,p,(n<=5000,m<=5000,p<=5000),分别表示有n个人,m个亲戚关系,询问p对亲戚关系。
以下m行:每行两个数Mi,Mj,1<=Mi,Mj<=N,表示Mi和Mj具有亲戚关系。
接下来p行:每行两个数Pi,Pj,询问Pi和Pj是否具有亲戚关系。
输出格式
P行,每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。
输入输出样例
输入 #1
1 | 6 5 3 |
输出 #1
1 | Yes |
代码模板:
1 |
|
洛谷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 | 100 7 |
输出 #1
1 | 3 |
说明/提示
1 ≤ N ≤ 5 ∗ 10^4
1 ≤ K ≤ 10^5
代码:
1 |
|