并查集

并查集

并查集

一、定义

并查集是一种树型的数据结构,用于处理一些不相交集合(disjoint sets)的合并及查询问题。

二、主要操作

  1. 初始化
    把每个点所在集合初始化为其自身。
    通常来说,这个步骤在每次使用该数据结构时只需要执行一次,无论何种实现方式,时间复杂度均为O(N)。
  2. 查找
    查找元素所在的集合,即根节点。可用于询问两个元素是否在同一个集合中。
  3. 合并
    将两个元素所在的集合合并为一个集合。
    通常来说,合并之前,应先判断两个元素是否属于同一集合,这可用上面的“查找”操作实现。

三、实现

基本原理:每个集合用一棵树来表示。树根的编号就是整个集合的编号,每个结点存储它的父节点,f[x]表示x的父节点。

  1. 如何判断是否是根: if(f[x]==x)
  2. 如何求x的集合编号: while(f[x]!=x) x=f[x];
  3. 如何合并两个集合:f[x]=y;

如果只是这样的话,会发现在求x的集合编号时的速度仍然比较慢,因此需要一些优化。

优化1:路径压缩

并查集在不断合并的过程中,可能会形成一条长长的,随着链越来越长,我们想要从底部找到根节点会变得越来越难。怎么解决呢?我们可以使用路径压缩的方法。既然我们只关心一个元素对应的根节点,那我们希望每个元素到根节点的路径尽可能短,最好只需要一步。

只要我们在查询的过程中,把沿途的每个节点的父节点都设为根节点即可。下一次再查询时,我们就可以省很多事。这用递归的写法很容易实现:

1
2
3
4
5
6
7
8
9
10
int find(int x)
{
if(x == f[x])
return x;
else
{
f[x] = find(f[x]); //父节点设为根节点
return f[x]; //返回父节点
}
}

优化2:按秩合并

现在我们有一棵较复杂的树需要与一个单元素的集合合并。我们应该把简单的树往复杂的树上合并,而不是相反。因为如果复杂的往简单的合并,会使树的深度(树中最长链的长度)加深,原来的树中每个元素到根节点的距离都变长了,之后我们寻找根节点的路径也就会相应变长。虽然我们有路径压缩,但路径压缩也是会消耗时间的。

我们用一个数组rank[]记录每个根节点对应的树的深度(如果不是根节点,其rank相当于以它作为根节点的子树的深度)。一开始,把所有元素的rank()设为1。合并时比较两个根节点,把rank较小者往较大者上合并。路径压缩和按秩合并如果一起使用,时间复杂度接近 O(N),但是很可能会破坏rank的准确性。

按树深度合并代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void merge(int i, int j)
{
int x = find(i), y = find(j); //先找到两个根节点
if (rank[x] <= rank[y])
{
f[x] = y;
//rank[y]+=rank[x];
}
else
{
f[y] = x;
//rank[x]+=rank[y];
}
if (rank[x] == rank[y] && x != y)
rank[y]++; //如果深度相同且根节点不同,则新的根节点的深度+1
}

按树的结点数量合并:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void merge(int i, int j)
{
int x = find(i), y = find(j); //先找到两个根节点
if (rank[x] <= rank[y])
{
f[x] = y;
rank[y]+=rank[x];
}
else
{
f[y] = x;
rank[x]+=rank[y];
}
}

四、例题和完整模板

洛谷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
2
3
4
5
6
7
8
9
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6

输出 #1

1
2
3
Yes
Yes
No

代码模板:

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
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100050;
int fa[N],cnt[N];
int n,m,p;
int find(int x)//找到点的根节点
{
if(x==fa[x])return x;
fa[x]=find(fa[x]);//路径压缩,在查找根的过程中把树链上的每一个点都直接设为根节点的儿子
return fa[x];
}
void merge(int a,int b)//合并
{
int x=find(a),y=find(b);
if(cnt[x]>=cnt[y])
{
fa[y]=x;
cnt[x]+=cnt[y];
}//按秩合并
else
{
fa[x]=y;
cnt[y]+=cnt[x];
}
}
int query(int a,int b)//查询两个点是否在同一个集合中
{
if(find(a)==find(b))return 1;
return 0;
}
int main()
{
ios::sync_with_stdio(0);
cin>>n>>m>>p;
for(int i=1;i<=n;i++)
{
fa[i]=i;//初始化,一开始每个集合只有自己一个元素
}
int a,b;
for(int i=1;i<=m;i++)
{
cin>>a>>b;
merge(a,b);
}
for(int i=1;i<=p;i++)
{
cin>>a>>b;
if(query(a,b))cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}

洛谷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
2
3
4
5
6
7
8
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

输出 #1

1
3

说明/提示

1 ≤ N ≤ 5 ∗ 10^4

1 ≤ K ≤ 10^5

代码

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
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<cstdio>
using namespace std;
const int N=50050;
int n,k;
int fa[N];
int d[N];
int ans=0;
int find(int x)
{
if(fa[x]==x)return x;
int t=find(fa[x]);
d[x]+=d[fa[x]];
fa[x]=t;
return fa[x];
}

/*核心:记录每一个点和根节点之间的关系,就能够确定任意两个点之间关系
算法思想:用并查集维护关系的同时,记录额外的信息
** 难点:建模--由于是三种动物轮流吃,考虑记录每个点到根节点的距离来确定关系。
到根节点距离是1,可以吃根节点 mod 3=1
距离是2,可以被根节点吃 mod 3=2
距离是3/0,和根节点同类 mod 3=0
这里根节点作为一个中转!
*/
int main()
{
ios::sync_with_stdio(0);
cin>>n>>k;
int op,x,y;
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
for(int i=1;i<=k;i++)
{
cin>>op>>x>>y;
if(x>n or y>n)
{
ans++;
continue;
}//情况2
int fx=find(x),fy=find(y);
if(op==1)
{
if(fx==fy and (d[x]-d[y])%3)ans++;
else if(fx!=fy)//之前不在同一个集合说明没有关系,不会冲突
{
fa[fx]=fy;//建立联系
d[fx]=d[y]-d[x];//使得连起来后能对3同余
//在下次find时会路径压缩,d[x]就会变成d[y]
}
}
else
{
if(fx==fy and (d[x]-d[y]-1)%3)ans++;
else if(fx!=fy)
{
fa[fx]=fy;//建立联系
d[fx]=d[y]+1-d[x];//与合并步骤类似的思想
}
}
}
cout<<ans;
return 0;
}
//洛谷题解中另外的方法:维护一个三倍空间的并查集来记录关系信息
//这种用距离来维护关系的方法是 带权并查集