在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受，只能采用一种全新的抽象的特殊数据结构——并查集来描述。

初始化

把每个点所在集合初始化为其自身。father[i]=i;

通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(N)。

查找

查找元素所在的集合，即根节点。

合并

将两个元素所在的集合合并为一个集合。

通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。

[Stupid]愚蠢的宠物

题目描述

背景

大家都知道，sheep有两只可爱的宠物（一只叫神牛，一只叫神菜）。有一天，sheep带着两只宠物到狗狗家时，这两只可爱的宠物竟然迷路了……

描述

狗狗的家因为常常遭到猫猫的攻击，所以不得不把家里前院的路修得非常复杂。狗狗家前院有N个连通的分叉结点，且只有N-1条路连接这N个节点，节点的编号是1-N（1为根节点）。sheep的宠物非常笨，他们只会向前走，不会退后（只向双亲节点走），sheep想知道他们最早什么时候会相遇（即步数最少）。

N的范围《=1000000

输入格式第1行：一个正整数N，表示节点个数。

第2~N行：两个非负整数A和B，表示A是B的双亲。（保证A,B<=n）

第N+1行：两个非负整数A和B，表示两只宠物所在节点的位置。（保证A,B<=n）

输出格式输出他们最早相遇的节点号。

样例输入

10
1 2
1 3
1 4
2 5
2 6
3 7
4 8
4 9
4 10
3 6

样例输出

1

代码（这题我觉得和并查集没多大关系。。）

#include<iostream>

#include<cstring>

using namespace std;

int father[1000000];

int a[1000000],b[1000000];//a[i]与b[i]分别记录俩只宠物到i结点的步数

int main()

{

memset(a,127/3,sizeof(a));

memset(b,127/3,sizeof(b));

int x,y;

int n;

cin>>n;

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

father[i]=i; //初始每个元素的父亲指针指向本身

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

{

cin>>x>>y;

father[y]=x;

}

cin>>x>>y;

for(int i=0;i<n;i++)

{

a[x]=min(i,a[x]);

x=father[x];

b[y]=min(i,b[y]);

y=father[y];

}

int mn=999999,ans;

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

{

if(a[i]+b[i]<mn){mn=a[i]+b[i];ans=i;}//求在哪个结点相遇总步数最短

}

cout<<ans;

return 0;

}

亲戚（家族）

题目描述

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

输入格式

第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。

以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有亲戚关系。

接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。

输出格式

P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

样例输入

6 5 3

1 2

1 5

3 4

5 2

1 3

1 4

2 3

5 6

样例输出

Yes

Yes

No

代码（这题是并查集的经典问题）

#include <iostream>

using namespace std;

int father[20001];

int m,n,i,x,y,q;

int find(int x)//用于查找一个元素的所在集合即根节点

{

if(father[x]!=x)

father[x]=find(father[x]);//路径压缩，递归将路径上的元素父亲指针都指向根节点

return father[x];

}

void u(int r1,int r2)//合并两个集合

{

father[r2]=r1;

}

int main()

{

cin>>n>>m>>q;

for(i=1;i<=n;i++)

father[i]=i;//初始每个元素的父亲指针指向本身

for(i=1;i<=m;i++)

{

cin>>x>>y;

int r1=find(x);

int r2=find(y);

if(r1!=r2)u(r1,r2);//合并两个元素的根节点

}

for(i=1;i<=q;i++)

{

cin>>x>>y;

if(find(x)==find(y))cout<<“Yes”<<endl;//判断两个元素的所在集合即根节点是否相同

else cout<<“No”<<endl;

}

return 0;

}

mty的考验

题目描述

啊!几经周折.mty终于找到了他的偶像.他就是….fyc!

可是fyc这样的高级人士可不喜欢一个人总是缠着他.于是他出了一道难题想考考mty.fyc有几个手下:陈乐天,舒步鸡,胡巍……现在fyc要去和别人fight,需要组建一值军队.军队的士兵在fyc的手下里选.

要组建一个军队,必修满足军队中的每个人之间都有直接或间接的朋友关系.

那么mty现在需要组建一支在满足上述情况下的人数最多的军队.

问题规模:

对于100%的数据,1<=n<=1000,1<=m<=500.

输入格式第一行,两个数,n,m.(n表示fyc有几个手下m表示有m对朋友关系).

一下m行,每行两个数.x[i],y[i].表示编号为x[i],y[i]的人是朋友.

输出格式一个数,表示人数最多的军队的人数.

样例输入

5 3
1 2
2 3
3 4

样例输出

4
说明:1,2,3,4可组成一直军队.

代码

#include<iostream>

using namespace std;

int father[1001];

int find(int x)

{

if(x!=father[x])father[x]=find(father[x]);

return father[x];

}

void un(int f,int z)

{

father[z]=f;

}

int main()

{

int a[1001]={0};

int ans=0;

int n,m;

int x,y;

cin>>n>>m;

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

{

father[i]=i;

}

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

{

cin>>x>>y;

un(find(x),find(y));

}

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

{

a[find(i)]++;

ans=max(a[find(i)],ans);

}

cout<<ans;

//system(“pause”);

return 0;

}

约会计划

题目描述

cc是个超级帅哥，口才又好，rp极高（这句话似乎降rp），又非常的幽默，所以很多mm都跟他关系不错。然而，最关键的是，cc能够很好的调解各各妹妹间的关系。mm之间的关系及其复杂，cc必须严格掌握她们之间的朋友关系，好一起约她们出去，cc要是和不是朋友的两个mm出去玩，后果不堪设想……

cc只掌握着一些mm之间的关系，但是cc比较聪明，他知道a和b是朋友，b和c 是朋友，那么a和c也是朋友。

下面给出m对朋友关系, cc 定了p次约会，每次约会找两个mm，如果这两个mm是朋友，那么不会出乱子，输出‘safe’，要是不是朋友，那么cc必然会挨……，输出‘cc cry’（T_T）。

「数据范围」

0<m<=2008

0<p<=2008

输入格式第一行为n，m，p。n为mm的数量，cc知道m对朋友关系，有p次约会。

2到n+1 行，每行一个字符串，为第i个mm的名字。{字符串长度<=11,且全大写}

以下m行，每行两个字符串，用空格隔开 ，为有朋友关系的两个mm的名字。

以下p行，每行为两个字符串，用空格隔开，为这p次约会中两个mm的名字。

{保证数据不会出现没有出现过的名字}

输出格式输出P行表示第i次约会的情况，输出‘safe’或者‘cc cry’

样例输入

3 1 1
AAA
BBB
CCC
AAA CCC
AAA BBB

样例输出

cc cry

代码

#include<iostream>

using namespace std;

string mm[2009];

int n,m,p;

int father[2009];

int get(string a)

{

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

{

if(mm[i]==a)return i;

}

}

int find(int x)

{

if(x!=father[x])father[x]=find(father[x]);

return father[x];

}

int un(int x,int y)

{

father[x]=y;

}

int main()

{

string a,b;

cin>>n>>m>>p;

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

{

cin>>mm[i];

father[i]=i;

}

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

{

cin>>a>>b;

un(find(get(a)),find(get(b)));

}

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

{

cin>>a>>b;

if(find(get(a))==find(get(b)))cout<<“safe”<<endl;

else cout<<“cc cry”<<endl;

}

return 0;

}