posts - 274,  comments - 1258,  trackbacks - 0
标程：并查集API

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 踏雪赤兔 阅读(714) 评论(0)  编辑 收藏 引用 所属分类: 零件仓库
只有注册用户登录后才能发表评论。
Copyright ©2024 踏雪赤兔 Powered By: 博客园 模板提供：沪江博客

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

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

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

常用链接

随笔分类(300)

随笔档案(274)

文章分类(38)

相册

收藏夹(54)

与博主互动

博客手拉手

搜索

  •  

积分与排名

  • 积分 - 392918
  • 排名 - 10

最新评论

阅读排行榜

评论排行榜