并查集学习总结

2014年1月7日1,8940

在一些有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;

}