例題洛谷P2978
用途：判斷圖中有幾個(gè)連通塊
1.int pre[1000]; 記錄了每個(gè)人的上級是誰练慕。如果一個(gè)人的上級就是他自己铃将，那說明他就是隊(duì)長，一個(gè)塊只能有一個(gè)隊(duì)長
2.查找
int find(int x)
{
if(pre[r]==r)
return r;
else find(pre[r]);
}
3.合并
void join(int x,int y)
{
int fx=find(x), fy=find(y);
if(fx != fy)
pre[fx]=fy;
}
4.路徑壓縮
因?yàn)椴魂P(guān)心連通的結(jié)構(gòu)绘盟，有可能是個(gè)很長的鏈狀結(jié)構(gòu)龄毡，理想的狀況是沦零，所有人的上級都是自己隊(duì)伍里面的隊(duì)長偎捎，這樣需要只要一次操作就能判斷是否是一個(gè)隊(duì)伍的茴她。
因此，每次根據(jù)每個(gè)點(diǎn)查找到隊(duì)長后將該點(diǎn)的上級設(shè)為隊(duì)長祭钉。
同時(shí)為了使合并后的樹不再退化慌核，即合并后層數(shù)盡量不變申尼，可以用rank[1000]表示樹的層數(shù)
改進(jìn)后的代碼
int pre[1000];
int rank[1000];
//初始化
for(int i=0;i<n;i++)
{
pre[i]=I;
rank[I]=0;
}
//查找函數(shù)
int find(int x)
{
if(pre[x] == x){
return x;
}
return pre[x] =find (pre[x]);
}
//合并函數(shù)
void Union(int i,int j)
{
i=find(i);
j=find(j);
if(i==j) return ;
if(rank[i]>rank[j]) pre[j]=i;
else
{
if(rank[i]==rank[j]) rank[j]++;
pre[i]=j;
}
}
