并查集（Union-Find Sets）的兩種功能：合并兩個(gè)集合；查找一個(gè)元素屬于哪個(gè)集合。
并查集的兩個(gè)優(yōu)化：基于rank的啟發(fā)式合并；路徑壓縮。
以下是我的代碼:
#include<stdio.h>
const long maxn=10008;
long n,f[maxn],rank[maxn];
void Init()
{
for(long i=1;i<=n;i++)
{
f[i]=i;
rank[i]=0;
}
}
long Getf(long x)
{
if(f[x]==x) return x;
f[x]=Getf(f[x]);// 路徑壓縮
return f[x];
}
bool Same(long x,long y)
{
return (Getf(x)==Getf(y));
}
void Union(long x,long y)
{
long fx=Getf(x),fy=Getf(y);
if(fx!=fy)
{
if(rank[fx]==rank[fy])
{
f[fx]=fy;
rank[fy]++;
}
else if(rank[fx]<rank[fy])
f[fx]=fy;
else f[fy]=fx;
}// 啟發(fā)式合并
}
int main()
{
n=10;
Init();
return 0;
}