lzh

刘政
posts - 17, comments - 1, trackbacks - 0, articles - 1

并查集

Posted on 2010-10-16 15:51 lzh525 阅读(2298) 评论(1)  编辑 收藏 引用 所属分类: ACM解题报告
 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 }

Feedback

# re: 并查集  回复  更多评论   

2013-08-31 10:20 by 龚细军
文章不错.....能有个图,就更好了!

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理