并查集模板：
#include<iostream>
using namespace std;
int Rank[],x,y;
int v[];
//初始化 x 集合
void init(int n)
{
for(int i=; i<n; i++)
{
v[i]=i;
Rank[i]=;
}
}
//查找 x 所在的集合
int find_set(int x)
{
if(v[x]!=x) v[x]=find_set(v[x]);
return v[x];
}
///更新根节点，有可能会暴栈
int mix(int x,int y)
{
int fx,fy;
fx=find_set(x);
fy=find_set(y);
if(fx!=fy)
p[fx]=fy;
}
//合并 x， y 所在的集合，用到路径压缩，按秩合并
void Union(int x,int y)
{
x=find_set(x);
y=find_set(y);
if(Rank[x]>Rank[y])
v[y]=x;
else if(Rank[x]<Rank[y])
v[x]=y;
else if(Rank[x]==Rank[y])
{
v[x]=y;
Rank[y]++;
}
}
int main()
{
return ;
}
模板
计算环的个数,需要缩点：
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <sstream>
#include <algorithm>
#define maxn 100010
#define INF 0x7fffffff
#include <queue>
#define N 1000010
#define ll __int64
#define mem(a,b) memset(a,b,sizeof(a))
#define repu(i, a, b) for(int i = (a); i < (b); i++)
const double PI=-acos(-1.0);
using namesPce std;
///初始化 x 集合
int P[maxn],Rank[maxn];
void mix()
{
repu(i,,maxn)
{
P[i]=i;
Rank[i]=;
}
}
///查找 x 所在的集合
int find_set(int x)
{
if(P[x]!=x)
P[x]=find_set(P[x]);
return P[x];
}
///缩点，合并 x， y 所在的集合，用到路径压缩，按秩合并
void Union(int x,int y)
{
x=find_set(x);
y=find_set(y);
if(Rank[x]>Rank[y])
P[y]=x;
else if(Rank[x]<Rank[y])
P[x]=y;
else if(Rank[x]==Rank[y])
{
P[x]=y;
Rank[y]++;
}
}
int main()
{
int x,y;
while(scanf("%d",&x) == )
{
mix();
int refu = ;
while(x!=-)
{
scanf("%d",&y);
x = find_set(x);
y = find_set(y);
if(x == y)///如果同一个根节点，就是环
++refu;
else
Union(x,y);
scanf("%d",&x);
}
printf("%d\n",refu);
}
return ;
}
UVALA3644 find_set + Union
计算联通块的个数
题意：n个结点，m条边，求再连几条边能使得全部结点连通；
思路：并查集，求该图中有几个连通分支，然后连通块的个数-1；
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int p[];
int n,m;
int a,b;
int find_set(int x)
{
return p[x]==x?x:find_set(p[x]);
}
void mix(int x,int y)
{
int fx,fy;
fx=find_set(x);
fy=find_set(y);
if(fx!=fy)
p[fx]=fy;
}
int main()
{
int cas=;
while(scanf("%d",&n)&&n)
{
scanf("%d",&m);
int count=;
for(int i=; i<=n; i++)
p[i]=i;
for(int j=; j<=m; j++)
{
scanf("%d%d",&a,&b);
mix(a,b);
}
for(int i=; i<=n; i++)
if(p[i]==i) count++;
printf("%d\n",count-);
}
return ;
}
HDU 1232 find_set + mix
计算每个连通块个数，取最大：
#include<cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
struct A
{
int num,pre;
} Set[];
void init(int n)///初始化
{
int i;
for(i=; i<=n; i++)
{
Set[i].num=;
Set[i].pre=i;
}
}
int Find(int k)///找根节点
{
if(Set[k].pre==k)
return k;
return Set[k].pre = Find(Set[k].pre);
}
int main()
{
int n,maxn,ans,i,f1,f2;
int x[],y[];
while(~scanf("%d",&n))
{
if(n==)
{
printf("1\n");
continue;
}
maxn=;
for(i=; i<=n; i++)
{
scanf("%d%d",&x[i],&y[i]);
maxn = max(maxn,max(x[i],y[i]));
}
init(maxn);
for(i=; i<=n; i++)
{
f1=Find(x[i]);
f2=Find(y[i]);
if(f1!=f2)
{
Set[f1].pre=f2;
Set[f2].num += Set[f1].num;///把该节点的子节点加上
}
}
ans=;
for(i=; i<=maxn; i++)
ans=max(ans,Set[i].num);
printf("%d\n",ans);
}
return ;
}
HDU 1856 find_set