DISJOINT-SET (CẤU TRÚC DỮ LIỆU)

[ductam]

Một cấu trúc dữ liệu rất hữu dụng trong lý thuyết đồ thị ,cũng như các bài tập trong OLP và các "constest online", đó là DISJOINT-SET.
Link tham khảo thêm: http://en.wikipedia.org/wiki/Disjoint_sets
Các bạn có thể tham khảo link trên và dùng Google search thêm, Mình chỉ nói đơn giản như sau :
Các phép toán trong DISJOINT-SET:
- Create(x) - Khỏi tạo cây có gốc là x
- Find(x) - Tìm gốc của nút x
- Union(x,y) - Hợp cây chứa nút x và cây chứa nút y.
Đề cài đặt có hiệu quả, chúng ta có hai heusrictics: Union by rank và Path Compress.
Sau đây mình chỉ nói về Union by rank.
Để tránh suy biến thì ta có quy tắc hợp hai cây như sau, cây nào mà nút gốc có rank lớn hơn thì sẽ là nút gốc của cây kia.

Các phép toán được cài đặt chi tiết như sau:

Code:


void Create(int x)
{
 rank[x]=0;
 P[x]=x;   
}
int Find(int x)
{
 if(x==P[x]) return x;
 return Find(P[x]); 
}
void Union(int x,int y)
{
 int px=Find(x);   
 int py=Find(y);
 if(rank[px]>rank[py]) P[py]=px;
 else P[px]=py;
 if(rank[px]==rank[py]) rank[py]++;
}


Các bạn thấy cài đặt cực kì đơn giản nhưng có tầm ứng dụng rất rộng rãi và mạnh mẽ trong nhiều bài toán.
Bài toán vận dụng:
Trong một hội nghị cấp cao, Người A quen với B, B quen với C thì A cũng sẽ quen với C. Như vậy sau hội nghị người i, có quen người j không?