并查集通過一個一維數組來實作,它的本質是維護一個森林,剛開始的時候,森林的每個點都是孤立的,也可以了解為每個點就是一棵隻有一個節點的樹,之後通過一些條件,逐漸将這些樹合并成一棵大樹。其實合并的過程就是“認爹”的過程。在“認爹”的過程中,要遵守“靠左”原則和“擒賊先擒王”的原則。在每次判斷兩個節點是否已經在同一棵樹的時候(一棵樹其實就是一個集合),也要注意必須求其根源,中間父親節點是不能說明問題的,必須找到其祖宗(樹的根節點),判斷兩個節點的祖宗是否是同一個根節點才行。并查集其實就是在“找祖宗”。
模闆:
#include<stdio.h>
int f[10010],n,m;
void init() //初始化
{
int i;
for(i=1;i<=n;i++)
f[i]=i;
return;
}
//找爹的遞歸函數,不停地去找爹,直到找到祖宗為止
int getf(int v)
{
if(f[v]==v)
return v;
else
{
//這裡是路徑壓縮,每次在函數傳回的時候,順帶把路上遇到的人的“父親 ”改為最後找到的祖宗的編号
f[v]=getf(f[v]);
return f[v];
}
}
void merge(int x,int y)
{
int t1,t2;
t1=getf(x);
t2=getf(y);
if(t1!=t2) //判斷兩個節點是否在同一個集合中,即是否是同一個祖先
{
f[t2]=t1; //靠左原則
}
return;
}
int main()
{
int i,a,b,sum;
scanf("%d%d",&n,&m);
init();
sum=0;
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
merge(a,b);
}
for(i=1;i<=n;i++)
{
if(f[i]==i)
sum++;
}
printf("%d\n",sum);
}