随笔-20  评论-16  文章-36  trackbacks-0
并查集
class UnionNS{
public:
    int maxV;
    int* p;
    UnionNS( int v ){
        maxV= v;
        p= new int[maxV];
        memset(p,-1,sizeof(int)*maxV);
    }
    // 求根运算： 
    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;
    } 
    // 判断等价 
    bool equal( int i, int j ){
        return root(i)==root(j);
    } 
    // 求集合规模 
    int size( int i ){
        return  -p[root(i)];
    } 
    // 合并 
    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;
        }
    } 
};
posted on 2009-03-17 22:16 古月残辉 阅读(172) 评论(0)  编辑 收藏 引用 所属分类: Template

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


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 古月残辉