posts - 274,  comments - 1258,  trackbacks - 0

namespace  UnionNS {
    
/* 解决:并查集
     *算法:树状、带路径压缩的并查集
     *备注:by Cockerel 06-08-27
     
*/

    
const   int  maxV = 100 ;
    
int  p[maxV]; // p[i]= p[i]>=0 ? 父编号 : 集合规模
    
// 初始化:
    inline  void  init() {
        memset(p,
- 1 , sizeof (p)); // 初始化为根且规模为1
    }

    
// 求根运算:
    inline  int  root( int  i) {
        
int  j,r;
        
for (r = i; p[r] >= 0 ; r = p[r]);
        
for (; i != r; i = j)
            j
= p[i],p[i] = r; // 路径压缩
         return  r;
    }

    
// 判断等价
    inline  bool  equal( int  i,  int  j) {
        
return  root(i) == root(j);
    }

    
// 求集合规模
    inline  int  size( int  i) {
        
return   - p[root(i)];
    }

    
// 合并
    inline  void  merge( int  i,  int  j) {
        i
= root(i); j = root(j);
        
if (i == j)  return ;
        
if (p[i] < p[j]) // 树状合并
            p[i] += p[j], p[j] = i;
        
else
            p[j]
+= p[i], p[i] = j;
    }

}

  树状合并、带路径压缩的并查集可以以最大O(logN),平均O(1)的复杂度完成合并与测试操作
  这个是2006年11月15日更新版,相比于2006年7月8日版,有以下改进:
  1、添加求集合规模运算
  2、简化代码
  3、提高运行速度
  4、减少占用空间
      相比于2006年8月8日版,修改了一个小bug。
  该标程经VC6.0及g++编译器编译通过。

posted on 2006-07-09 02:29 踏雪赤兔 阅读(702) 评论(0)  编辑 收藏 引用 所属分类: 零件仓库
只有注册用户登录后才能发表评论。

百度空间| 见闻日记| 编程感悟
我的twitter


LOGO

自我介绍:百度厂基础平台车间的一名挨踢民工。擅长C++、算法、语言设计、分布式计算,也用过Java,Python, PHP,JS/AS等语言开发。请关注我的twitter (免翻墙版) 发QQ消息


添加到收藏夹 Locations of visitors to this page

常用链接

随笔分类(300)

随笔档案(274)

文章分类(38)

相册

收藏夹(54)

与博主互动

博客手拉手

搜索

  •  

积分与排名

  • 积分 - 385860
  • 排名 - 10

最新评论

阅读排行榜

评论排行榜