Dijoint set

Các phép toán trên Dijoint set:

• MakeSet(x): Khởi tạo một tập con 1 phần tử {x}.
• MergeSet(x,y): Hợp nhất hai tập con chứa x, y lại.
• FindSet(x):Tìm gốc của tập hợp chứa x.

Cài đặt:

• Gọi p[x] là nút cha của x.
• rank[x] là chiều sâu của nút x khi đi từ gốc.
• Khởi tạo, p[x] = x, rank[x] = 0, mọi x.
• MergerSet(x,y):
• px = FindSet(x);
• py = FindSet(y);
• if(rank[px] > rank[py]) p[py] = px;
• else p[px] = py;
• if(rank[px]==rank[py]) rank[py] = rank[py] + 1;
• FindSet(x):
• if(x!=p[x]) return FindSet(p[x]);
• return x;

Code:


int p[101];
int rank[101];

void MakeSet(int NN)
{
for(int i=1;i<=NN;i++)
{
p[i]=i; rank[i]=0;
even[i]=1;
}
}
int FindSet(int x)
{
if(x!=p[x])return FindSet(p[x]);
return x;
}

void MergerSet(int x,int y)
{
int px = FindSet(x);
int py = FindSet(y);
if(rank[px]>rank[py])
p[py]=px;
else
p[px]=py;
if(rank[py]==rank[px])
rank[py]+=1;
}


Tham khảo:
http://en.wikipedia.org/wiki/Disjoint-set_data_structure
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure