并查集
数据结构——并查集的应用
并查集是一种简单的数据结构，相对于其他数据结构来说，编程难度很小，也很灵活，适当的find函数与Union函数便可以解决很多问题。
int find(int x)
{
if(x==parent[x]) return x;
returnparent[x]=find(parent[x]);
}
void Union(int a,int b)
{
intpa=find(a);
intpb=find(b);
if(pa!=pb) parent[pa]=pb;
}
并查集的应用：
并和查有关的集合操作
并查集可以用于相关的集合操作，如判定一个无向图是否有环，输出一个无向图的连通分量个数，kruscal最小生成树的操作。一些基于集合，有添加其它性质的集合操作。
例题：
TOJ2469 Friends
题目描述：有n个人，m对朋友关系，朋友关系对称且可传递，求有几个朋友圈。
分析：事实上是求一个无向图的连通分量数，并查集轻松搞定。
TOJ3294 Building Blcok
题目描述：一开始有n个Block，分别放置在地面上，有P个操作，操作有两种类型：
M a b如果a，b没有在一个Block组里，把包含a Block的Block组放在包含b的Block组之上。
C a 输出有多少个Block被压在了a之下。
分析：定义parent同并查集的一般操作，cnt表示有多少块Block[x]被压在x之下，size[x]表示以x为根的Block组一共有多少个Block.
#include <cstdio>
#include <cstring>
using namespace std;
#define MAX 30030
int par[MAX],cnt[MAX],size[MAX];
void init(int n)
{
for(int i=0;i<n;i++)
{
par[i]=i;
cnt[i]=0;
size[i]=1;
}
}
int find(int x)
{
if(x==par[x]) return x;
int tmp=par[x];
par[x]=find(par[x]);
cnt[x]+=cnt[tmp];
return par[x];
}
void Union(int a,int b,int pa,int pb)
{
par[pa]=pb;
cnt[pa]+=size[pb];
size[pb]+=size[pa];
}
int main()
{
int n,a,b,pa,pb;
char move[10];
while(scanf("%d",&n)!=EOF)
{
init(MAX);
for(int i=0;i<n;i++)
{
scanf("%s",move);
if(move[0]=='M')
{
scanf("%d%d",&a,&b);
pa=find(a);
pb=find(b);
if(pa!=pb) Union(a,b,pa,pb);
}
else if(move[0]=='C')
{
scanf("%d",&a);
find(a);
printf("%d\n",cnt[a]);
}
}
}
return 0;
}
TOJ3732 Dragon Balls
题目描述：悟空在寻找龙珠，一共有n个龙珠，m条操作。操作有两种。
T a b 表示把a龙珠所在的城里的所有龙珠运到b所在的城里
Q a 表示对a的询问，要求输出x a所在的城， y a所在的城里一共有多少个龙珠， z a经过几次到达现在所在的城的。
分析：定义parent同并查集的一般操作，step表示经过几步到达现在所在的城，size表示该城里的龙珠数。
#include <cstdio>
#include <cstring>
using namespace std;
#define MAX 10010
int par[MAX],step[MAX],size[MAX];
void init(int n)
{
for(int i=1;i<=n;i++)
{
par[i]=i;
step[i]=0;
size[i]=1;
}
}
int find(int x)
{
if(x==par[x]) return x;
int tmp=par[x];
par[x]=find(tmp);
step[x]+=step[tmp];
return par[x];
}
void Union(int a,int b)
{
int pa=find(a);
int pb=find(b);
par[pa]=pb;
size[pb]+=size[pa];
step[pa]++;
}
int main()
{
int T,n,m,a,b,t=1;
scanf("%d",&T);
while(T--)
{
printf("Case %d:\n",t++);
scanf("%d%d",&n,&m);
init(n);
for(int i=0;i<m;i++)
{
char move;
getchar();
move=getchar();
if(move=='T')
{
scanf("%d%d",&a,&b);
Union(a,b);
}
else
{
scanf("%d",&a);
int pa=find(a);
printf("%d %d %d\n",pa,size[pa],step[a]);
}
}
}
return 0;
}
种类相关并查集操作
题目中出现的元素分为一些种类，描述中会给出相关的描述信息，判断描述的正确性，即是否有悖于之前对这些元素种类的描述。一般可以增加一个kind属性来表示元素的种类。
例题：
POJ1182 食物链
题目大意：有A，B，C三种动物A吃B，B吃C，C吃A。有两种描
补充：综合编程 , 其他综合 ,
