在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能采用一种全新的抽象的特殊数据结构——并查集来描述。
定义：并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。集就是让每个元素构成一个单元素的集合，也就是按一定顺序将属于同一组的元素所在的集合合并。
初始化
描述：
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。
Input:
第一行：三个整数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是否具有亲戚关系。
OutPut:
P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。
方法一：单链表实现
一个节点对应一个人，在同一个集合中的节点串成一条链表就得到了单链表的实现。在集合中我们以单链表的第一个节点作为集合的代表元。于是每个节点x（x也是人的编号）应包含这些信息：指向代表元即表首的指针head[x]，指向表尾的指针tail[x]，下一个节点的指针next[x]。
|
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 |
#include<stdio.h>#include<stdlib.h>#define MAXSIZE 1000000int head[MAXSIZE],tail[MAXSIZE],next[MAXSIZE];//指向代表袁既表首指针，指向表尾指针，下一个节点的指针//建立单个人的集合 void
SUB_Make_Set(int
num){ int
i; for(i=1;i<=num;i++) { head[i]=i; tail[i]=i; next[i]=0; }}//确认x所在集合的代表元素 int
SUB_Find_Set(int
x){ return
head[x];} |
//将b所在的集合合并到a所在的集合
void SUB_Union(int a,int
b)
{
next[tail[head[a]]]=head[b];
tail[head[a]]=tail[head[b]];
int
p =
head[b];
while(p!=0)
{
head[p]=head[a];
p=next[p];
}
}
|
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 |
int main(){ int
n,m,p,i,mi,mj; scanf("%d%d%d",&n,&m,&p); SUB_Make_Set(n); printf("请输入%d组亲戚关系：\n",m); while(m--) { scanf("%d%d",&mi,&mj); if(SUB_Find_Set(mi)!=SUB_Find_Set(mj)) { SUB_Union(mi,mj); } } printf("请输入%d组询问亲戚关系：\n",p); while(p--) { scanf("%d%d",&mi,&mj); if(SUB_Find_Set(mi)==SUB_Find_Set(mj)) { printf("Yes\n"); } else { printf("NO\n"); } } return
0;} |
方法二：并查集深林
并查集的另一种更快的实现是用有根树来表示集合：每棵树表示一个集合，树中的节点对应一个人。
每个节点x包含这些信息：父节点指针p[x]，树的深度rank[x]。其中rank[x]将用于启发式合并过程。
还有另一种优化方法（未实现）：路径压缩：
|
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86 |
#include<stdio.h>#include<stdlib.h>#define MAXSIZE 1000000int p[MAXSIZE],rank[MAXSIZE];//父节点指针和深度//初始化节点 void
SUB_Make_Set(int
x){ p[x]=x; rank[x]=0;}//找出x的代表元素，既x树的根节点 （若两个节点的代表元素相同则说明这两个节点属于同一结合中）int
SUB_Find_Set(int
x){ if(x==p[x])//遇到根节点返回 { return
x; } else//递归查找 { return
SUB_Find_Set(p[x]); }}//合并a和b树 void
SUB_Union(int
a,int b){ int
pa,pb; //找出a树和b树的根节点 pa = SUB_Find_Set(a); pb = SUB_Find_Set(b); if(rank[pa]>rank[pb])//若a树的层数小于b树的层数，则将a树合并到b树中 { p[pb]=pa; } else//合作b树合并到a树中 { p[pa]=pb; if(rank[pa]==rank[pb])//若两树层次相等，则合并后层次要加1 { rank[pb]++; } } } int
main(){ int
n,m,p,i,mi,mj; scanf("%d%d%d",&n,&m,&p); for(i=1;i<=n;i++)//初始化离散的节点 { SUB_Make_Set(i); } printf("请输入%d组亲戚关系：\n",m); while(m--) { scanf("%d%d",&mi,&mj); if(SUB_Find_Set(mi)!=SUB_Find_Set(mj))//如果mi和mj还未属于同一集合中时需要进行合并操作 { SUB_Union(mi,mj); } } printf("请输入%d组询问亲戚关系：\n",p); while(p--) { scanf("%d%d",&mi,&mj); if(SUB_Find_Set(mi)==SUB_Find_Set(mj)) { printf("Yes\n"); } else { printf("NO\n"); } } return
0;} |
原文：http://www.cnblogs.com/fanling999/p/3595396.html