随笔 - 87  文章 - 279  trackbacks - 0
<2006年1月>
日一二三四五六
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

潜心看书研究！

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 214752
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

新学了并查集, 不知道能不能用呢^_^
#include  < iostream >
using   namespace  std;

 const   int  MAXN  =   100 ;

 class  UFset
 {
 public :
     int  parent[MAXN];
    UFset();
     int  Find( int );
     void  Union( int ,  int );
} ;

UFset::UFset()
 {
    memset(parent,  - 1 ,  sizeof (parent));
}

int  UFset::Find( int  x)
 {
     if  (parent[x]  <   0 )
         return  x;
     else
     {
        parent[x]  =  Find(parent[x]);
         return  parent[x];
    } //  压缩路径
}

void  UFset::Union( int  x,  int  y)
 {
     int  pX  =  Find(x);
     int  pY  =  Find(y);
     int  tmp;
     if  (pX  !=  pY)
     {
        tmp  =  parent[pX]  +  parent[pY];  //  加权合并
         if  (parent[pX]  >  parent[pY])
         {
            parent[pX]  =  pY;
            parent[pY]  =  tmp;
        }
         else
         {
            parent[pY]  =  pX;
            parent[pX]  =  tmp;
        }
    }
}

int  main()
 {
     return   0 ;
}
有bug请指正:)
posted on 2006-08-16 20:22 豪 阅读(889) 评论(5)  编辑 收藏 引用 所属分类: 算法&ACM

FeedBack:
# re: 新学了并查集, 不知道能不能用呢^_^ 2006-08-17 11:55 Optimistic
强~
  回复  更多评论
  
# re: 新学了并查集, 不知道能不能用呢^_^ 2006-08-23 08:57 cainiao
终于知道并查集了
....
谢....  回复  更多评论
  
# re: 新学了并查集, 不知道能不能用呢^_^ 2006-09-01 09:46 small-fat
呵呵，我也学一下..  回复  更多评论
  
# re: 新学了并查集, 不知道能不能用呢^_^ 2006-09-01 23:15 踏雪赤兔
写法严谨，但不够简洁。不适合作为acm标程使用。
parent[]数组是两用的。定义如下
if(parent[i]>=0) parent[i]是父结点编号
else i是根且-parent[i]是集合规模  回复  更多评论
  
# re: 新学了并查集, 不知道能不能用呢^_^ 2006-09-01 23:20 豪
你意思是再加个 int size(int i)函数返回 i所在集合大小？  回复  更多评论
  

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


Copyright ©2024 豪 Powered by: 博客园 模板提供：沪江博客