数据结构复习考试(7)

##介绍

并查集:(union-find sets)是一种简单的用途广泛的集合。并查集是若干个不相交集合,能够实现较快的合并和判断元素所在集合的操作,应用很多。

一般采取树形结构来存储并查集,并利用一个rank数组来存储集合的深度下界,在查找操作时进行路径压缩使后续的查找操作加速。这样优化实现的并查集,空间复杂度为O(N),建立一个集合的时间复杂度为O(1)。并查集的操作可以看作是线性的。

它支持以下几种操作:

  • void Init(int n)
  • void Union(int p, int q)
  • bool Connected(int p, int q)
  • int GetFather(int n)
  • int count()

##解决问题
并查集主要应用于涉及到几个不相交子集的查找和合并运算。

模板题:POJ1611 POJ2524 POJ1182 POJ2492 POJ1988

##模板

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
class UnionFind{
private:
vector<int> father;
vector<int> sum;//the number of child as root
public:
void Init(int n){
father.clear();
father.resize(n+2);//start from 1
sum.clear();
sum.resize(n+2);
for (int i=1; i<= n; i++){
father[i] = i;
sum[i] = 0;
}
}

bool Is_same(int x, int y){
return GetFather(x) == GetFather(y);
}

void Union(int x, int y){
father[GetFather(x)] = GetFather(y);
}

int GetFather(int x){
if (father[x] == x) return x;
else return father[x] = GetFather(father[x]);
}

int FindGroups(){
int ans = 0;
for (int i=1; i<=father.size()-2; i++){
sum[GetFather(i)]++;
}
for (int i=1; i<=father.size()-2; i++){
if (sum[i]) ans++;
}
return ans;
}
};

参考:
http://blog.csdn.net/dm_vincent/article/details/7769159
http://blog.csdn.net/dm_vincent/article/details/7655764