并查集:
实现了导论上面的伪代码的程序:
code:
1 #include<iostream>
2 using namespace std;
3 #define REP(i,from,to) for(int i=(from);i<=(to);++i)
4 struct disset{
5 int *d;
6 int *rank;
7 int l;
8 disset(int *_d,int *_rank,int _l):d(_d),rank(_rank),l(_l){
9 REP(i,0,l-1){
10 makeset(i);
11 }
12 };
13 void makeset(int i){
14 d[i]=i;
15 rank[i]=0;
16 }
17 void u3n(int x,int y){
18 link(find(x),find(y));
19 }
20 void link(int x,int y){
21 if(rank[x]>rank[y])
22 d[y]=x;
23 else{
24 d[x]=y;
25 if(rank[x]==rank[y])
26 rank[y]++;
27 }
28 }
29 int find(int x){
30 if(x!=d[x])
31 d[x]=find(d[x]);
32 return d[x];
33 }
34 };
35 int a[10];
36 int r[10];
37 int main(){
38 struct disset s(a,r,10);
39 s.u3n(0,1);
40 s.u3n(1,4);
41 s.u3n(5,6);
42 s.u3n(7,8);
43 s.u3n(4,5);
44 if(s.find(0) == s.find(6))
45 cout<<"GOOD!"<<endl;
46 REP(i,0,9)
47 cout<<r[i]<<' ';
48 cout<<endl;
49 return 0;
50 }
biVimium has been updated to
1.34.
x
posted on 2012-07-06 00:50
Gin 阅读(487)
评论(0) 编辑 收藏 引用 所属分类:
Introduction to algorithms