并查集（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 阅读(242)
评论(0) 编辑 收藏 引用 所属分类:
算法与数据结构