并查集详情总结

并查集

并查集：感觉就是一种高效的集合处理办法。

一.并查集实现：

按秩合并优化：

以HDU 1325 为例

#include


#include

#include

using namespace std;

const int N=1000;

int vis[N];

int uset[N],rank[N];

void make_set(int size)

{

for(int i=0;irank[y]) //秩小的，加在秩大的树上

uset[y]=x;

else

{

uset[x]=y;

if(rank[x]==rank[y])

rank[y]++;

}

}

int main()

{

int u,v;

int cas=0;

while(scanf("%d%d",&u,&v))

{

int maxx=0;

int ok=1;

if(u<0&&v<0)

break;

if(u==v&&v==0)

{

printf("Case %d is a tree.\n",++cas);

continue;

}

make_set(N);

memset(vis,0,sizeof(vis));

union_set(u,v);

if(u==v)

ok=0;

vis[v]=1;

while(scanf("%d%d",&u,&v),u||v)

{

if(v==u)

ok=0;

if(vis[v])

ok=0;

vis[v]=1;

union_set(u,v);

if(max(u,v)>maxx)

maxx=max(u,v);

}

int cnt=0;

for(int i=1;i<=maxx;i++)

if(uset[i]==i)

cnt++;

if(cnt>1) ok=0;

if(ok)

printf("Case %d is a tree.\n",++cas);

else

printf("Case %d is not a tree.\n",++cas);

}

return 0;

}

按树的大小优化：

以HDU 1856 为例

#include


#include

#include

#include

using namespace std;

const int N=100010;

int uset[N];

void make_set(int n)

{

for(int i=0;iint find(int x) { /非递归版



int p = x, t;

while (uset[p] >= 0) p = uset[p];

while (x != p) {

t = uset[x];

uset[x] = p;

x = t;

}

return x;

}

*/



void union_set(int x,int y)

{

if((x=find_set(x))==(y=find_set(y)))

return;

if(uset[x]

可以看出，这样合并实现了编号大的结点位于根节点。