并查集（Union-Find Sets）的兩種功能：合并兩個集合；查找一個元素屬于哪個集合。
并查集的兩個優化：基于rank的啟發式合并；路徑壓縮。
以下是我的代碼:
#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;
}// 啟發式合并
}
int main()
{
n=10;
Init();
return 0;
}
posted on 2010-01-06 18:05
lee1r 閱讀(254)
評論(0) 編輯 收藏 引用 所屬分類:
算法與數據結構