Posted on 2010-10-16 15:51
lzh525 阅读(2312)
评论(1) 编辑 收藏 引用 所属分类:
ＡＣＭ解题报告
1 /*并查集学习：
2
3 并查集：(union-find sets)
4
5 一种简单的用途广泛的集合. 并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多，如其求无向图的连通分量个数等。最完美的应用当属：实现Kruskar算法求最小生成树。
6
7 l 并查集的精髓（即它的三种操作，结合实现代码模板进行理解）：
8
9 1、unit(x) 把每一个元素初始化为一个集合
10
11 初始化后每一个元素的父亲节点是它本身，每一个元素的祖先节点也是它本身（也可以根据情况而变）。
12
13 2、find(x) 查找一个元素所在的集合
14
15 查找一个元素所在的集合，其精髓是找到这个元素所在集合的祖先！这个才是并查集判断和合并的最终依据。
16 判断两个元素是否属于同一集合，只要看他们所在集合的祖先是否相同即可。
17 合并两个集合，也是使一个集合的祖先成为另一个集合的祖先，具体见示意图
18
19 3、connect(x,y) 合并x,y所在的两个集合
20
21 合并两个不相交集合操作很简单：
22 利用find找到其中两个集合的祖先，将一个集合的祖先指向另一个集合的祖先。
23 并查集的优化
24
25 1、find(x)时 路径压缩
26 寻找祖先时我们一般采用递归查找，但是当元素很多亦或是整棵树变为一条链时，每次find(x)都是O(n)的复杂度，有没有办法减小这个复杂度呢？
27 答案是肯定的，这就是路径压缩，即当我们经过"递推"找到祖先节点后，"回溯"的时候顺便将它的子孙节点都直接指向祖先，这样以后再次find(x)时复杂度就变成O(1)了，如下图所示；可见，路径压缩方便了以后的查找。
28
29
30 2、connect(x,y)时 按秩合并
31 即合并的时候将元素少的集合合并到元素多的集合中，这样合并之后树的高度会相对较小。
32 */
33
34 #include<iostream>
35 using namesfatherace std;
36
37 int father[30001];//各个元素的父节点数组
38 int h[30001];//哥哥元素的高度
39
40 void Init(int n)
41 {
42 for(int i=0;i<n;i++)
43 {
44 father[i]=i;
45 h[i]=0;
46 }
47 }
48
49 int find(int x)
50 {
51 if(x!=father[x])
52 father[x]=find(father[x]);
53 return father[x];
54 }
55
56 void connect(int a,int b)
57 {
58 int x,y;
59 x=find(a);
60 y=find(b);
61 if(x==y)
62 return ;
63 if(h[x]<h[y])
64 father[x]=y;
65 else
66 {
67 if(h[x]==h[y])
68 h[x]++;
69 father[y]=x;
70 }
71 }
72
73 int main()
74 {
75 int k,a,i,m,n,num,t,first;
76 Init(20);
77 cin>>k;
78 while(k--)
79 {
80 cin>>m>>n;
81
82 connect(m,n);
83 }
84 for(i=1;i<=10;i++)
85 {
86 cout<<i<<"的父节点为: "<<father[i]<<" 高度:"<<h[i]<<endl;
87 }
88 return 0;
89 }