不相交集合數(shù)據(jù)結(jié)構(gòu)保持一組不相交的動態(tài)集合s={s1,s2,...}，每個集合通過一個代表來識別，代表是集合中的某個元素。
不相交集合的應(yīng)用較為經(jīng)典的是判斷會不會構(gòu)成連通圖，用于最小生成樹的Kruskal算法。
基本操作有：
make_set(x):建立一個新的集合，其唯一成員也就是代表為X。代表X都不同，起初各個集合肯定是不相交的。
union(x,y):將包含x,y元素的集合合并為一個新的集合，此時要選出一個新的代表來代表這個集合，并且將原先的包含x,y元素的集合刪除掉，將新集合加入到S中
find_set(x):返回包含x元素的集合的那個代表。
綜上所述，如何來選擇新集合的代表和find_set(x)將是我們要考慮到周密的問題。
接下來我們介紹按秩合并和路徑壓縮啟發(fā)式的方法來解決這個問題
看代碼分析吧：
#define N 1000
int p[N],rank[N];
void make_set(int x)
{
p[x]=x;
rank[x]=0;
}
void union(int x,int y)
{
if(rank[x]>rank[y])
p[y]=x;
else if(rank[x]<rank[y])
p[x]=y;
else if(rank[x]==rank[y]){
p[x]=y;
rank[y]++;
}
}
int find_set(int x)
{
if(x!=p[x])
p[x]=find_set(p[x]);
return p[x];
}
建議讀者好好幾個例子來分析下咯。。。