并查集
ACM竞赛中，并查集（DisjointSets）这个数据结构经常使用。顾名思义，并查集即表示集合，并且支持快速查找、合并操作。
用于高效的查找某两个元素是否属于同一个集合；
并查集如何表示一个集合？它借助树的思想，将一个集合看成一棵有根树。那又如何表示一棵树？初始状态下，一个元素即一棵树，根即是元素本身。
合并
并查集如何支持合并操作？不难发现，按照树的思想，在同一棵树中的所有元素，根都是相同的。也就是说，合并两个不同的集合，只需要将其中一个集合的根设置为另一个集合的根即可，而需要改变根的那个集合，其实只需要改变根节点的父节点即可。
如何支持快速查找操作
如果完全按照上面的合并方法进行合并操作，最后生成的树，可能是完全线性的，那么查询的时间复杂度就退化成了O(n)，因为在这种情况下，程序不得不遍历完所有节点才能查询到当前元素所属的根节点。
路径压缩算法优化并查集查询操作。按照集合原来的定义，集合中的元素是满足无序性的，因此可以在查询操作进行的过程中，当程序遍历到根节点然后返回的时候，将所有属于当前根节点的元素的父节点直接设置为当前根节点。如此一来，原来的一条链就变成了一般的树了。当下一次查询的时候，就可以很快的遍历到根节点了，复杂度下降为O(1)。
还有一种优化查询速度的方法，那就是合并两个集合的时候，按秩进行合并，这里的秩代表的以当前元素为根节点的元素个数。很明显，将秩较小的树合并到秩较大的树上更优。
最后，就是具体如何用代码实现并查集？其实，并查集中只涉及到了保存当前元素的父节点这一信息，所以利用一个数组set[i]代表节点i的父节点即可，如果set[i]=i那么代表当前集合的根即为i元素本身。
以一道例题为例，HDOJ：1212，时空转移（点击打开链接）：
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
| #include <cstdio>
const int NumSets = 1005;
typedef int DisjSet[NumSets + 1];
typedef int Rank[NumSets + 1];
DisjSet S;
Rank R;
void Initialize()
{
for(int i=0; i<NumSets; ++i)
{
S[i] = i;
R[i] = 1;
}
}
int Find(int value)
{
if(S[value] != value) S[value] = Find(S[value]);
return S[value];
}
void SetUnion(int value1, int value2)
{
int fa1 = Find(value1);
int fa2 = Find(value2);
if(fa1 == fa2) return ;
if(R[fa1] >= R[fa2])
{
S[fa2] = fa1;
R[fa1] += R[fa2];
}
else
{
S[fa1] = fa2;
R[fa2] += R[fa1];
}
}
int main()
{
int cas;
scanf("%d", &cas);
while(cas--)
{
int n, m;
Initialize();
scanf("%d%d", &n, &m);
for(int i=0; i<m; ++i)
{
int a, b;
scanf("%d%d", &a, &b);
if(Find(a) != Find(b))
{
SetUnion(a, b);
--n;
}
}
printf("%d\n", n);
}
return 0;
}！
|
摘自(https://blog.csdn.net/u011787119/article/details/46834903)
例题
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
| #include <stdio.h>
int f[1001]={0},n,m,sum=0;
void init(){
int i;
for(i=1;i<=n;i++)
f[i]=i;
return;
}
int getf(int v) {
if(f[v]==v) return v;
else{
f[v]=getf(f[v]);
return f[v];
}
}
int findFather(int v){
int node = v;
while ( arr[v] != v ) {
v = arr[v];
}
while ( node != arr[node] ){
int tmp_node = node;
node = arr[node];
arr[tmp_node] = v;
}
return v;
}
void merge(int v,int u) {
int t1,t2;
t1=getf(v);
t2=getf(u);
if( t1!=t2 )
f[t2]=t1;
return;
}
int main(){
int i,x,y;
scanf("%d %d",&n,&m);
init();
for(i=1;i<=m;i++){
scanf("%d %d",&x,&y);
merge(x,y);
}
for(i=1;i<=n;i++){
if(f[i]==i)
sum++;
}
printf("%d\n",sum);
getchar();getchar();
return 0;
}
|
用并查集判断无向图的连通性(或求连通分支个数)~
给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。
输入：每组数据的第一行是两个整数n 和m（0< n <=1000）。n 表示图的顶点
数目，m 表示图中边的数目。如果n 为0 表示输入结束。随后有m 行数据，每
行有两个值x 和y（0<x, y <=n），表示顶点x 和y 相连，顶点的编号从1 开始计
算。输入不保证这些边是否重复。
输出：对于每组输入数据，如果所有顶点都是连通的，输出 ’YES’ ，否则输
出 ’NO’。
1
2
3
4
5
6
7
8
9
10
11
12
| ===样例输入===
4 3
1 2
2 3
3 2
3 2
1 2
2 3
0 0
===样例输出===
NO
YES
|
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
| #include<stdio.h>
int map[1005];
int n,m;
int find(int i){
return map[i]==i?i:find(map[i]);
}
void init(){
for(int i=0;i<n;i++)
map[i]=i;
}
int main()
{
while(scanf("%d%d",&n,&m)==2)
{
if(n==0) break;
init();
int a,b;
for(int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
a--;b--;
map[find(a)]=map[find(b)];
}
int cnt=0;
for(int i=0;i<n;i++)
{
if(map[i]==i)
cnt++;
}
if(cnt==1)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
|
例子
题目链接：http://poj.org/problem?id=1611
题目大意： 中文就不解释了；
做法：把同一个集合的所有元素都放到同一个集合里， 当放完之后， 检查一下0号同学在哪个集合， 再判断一下剩下的同学是否和它在同一个集合里面；
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
|
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <sstream>
#include <stack>
#include <vector>
#define clr(x) memset(x, 0, sizeof(x))
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxm = 505;
const int maxn = 30000 + 10;
typedef long long int ll;
int n, m;
int pa[maxn];
int find(int x){
return x == pa[x] ? x : pa[x] = find(pa[x]);
}
void connect(int x, int y){
int fa = find(x);
int fb = find(y);
pa[fa] = fb;
}
int main(void) {
#ifdef LOCAL
#endif
while(scanf("%d%d", &n, &m) == 2 && (n || m)){
for(int i = 0; i < n; i++) pa[i] = i;
for(int i = 0; i < m; i++){
int len; scanf("%d", &len);
int x; scanf("%d", &x);
int tp = x;
for(int i = 1; i < len; i++){
scanf("%d", &x);
connect(x, tp);
tp = x;
}
}
int ans = 0;
int p = find(0);
for(int i = 0; i < n; i++)
if(find(i) == p)
ans++;
printf("%d\n", ans);
}
return 0;
}
|
