posts - 217, comments - 61, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Union Find Set

Posted on 2007-10-21 15:51 魔のkyo 阅读(367) 评论(0)  编辑 收藏 引用 所属分类: DataStucture
const int MaxSize = 100000;

class UFSets {
private:
    
int parent[MaxSize+1];
    
int size;
public:
    UFSets (
int s ){
        size 
= s;
        memset(parent,
-1,sizeof(parent));
    }
    
    
int Find (int x){
        
if ( parent[x] <0 ) return x;
        
else return Find (parent[x]);
    }
    
    
void   Union (int v1, int v2){
        
int s1=Find(v1),s2=Find(v2);
        
if(s1==s2)return;
        
int t = parent[s1] + parent[s2];
        
if ( parent[s2] < parent[s1] ) {
            parent[s1] 
= s2;
            parent[s2] 
= t;
        }
        
else { 
            parent[s2] 
= s1;
            parent[s1] 
= t;
        }
    }

    
int Count (int x){
        
return -parent[Find(x)];
    }
};
只有注册用户登录后才能发表评论。