Posted on 2007-10-21 15:51
魔のkyo 阅读(421)
评论(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)];
}
};