重剑无锋
我生待明日,万事成蹉跎
posts - 13,  comments - 6,  trackbacks - 0
并查集:
实现了导论上面的伪代码的程序:
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 }
posted on 2012-07-06 00:50 Gin 阅读(487) 评论(0)  编辑 收藏 引用 所属分类: Introduction to algorithms

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



<2012年7月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿

随笔分类

随笔档案

friends

  • figoSB
  • 除了我...谁敢叫韩飞sb...

搜索

  •  

最新评论

阅读排行榜

评论排行榜