SOJ4480 Easy Problem IV （并查集）

Easy Problem IV （并查集）"/>

SOJ4480 Easy Problem IV （并查集）

Time Limit: 3000 MS    Memory Limit: 131072 K

Description

据说 你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。现在有n个互不认识的人
对于这一群人 我们要实现两个操作1.介绍两个人互相之间认识，由于这n个人都非常热情好客 他们会介绍所有自己认识的人给对方 也会介绍给所有对方认识的人也就是说 若 A 和 B 认识 ，C 和 D 认识，若我们介绍A和C认识 那么B和D也会互相认识
2.询问 某两个人 是否认识对方

Input

为多组数据
第一行为一个数 代表有多少组数据对于每一组数据 
第一行有两个数n m 分别代表有多少个人 和 多少个操作
接下来m行
对于每一行的第一个数 为1 或 2 代表当前操作是哪一类操作
若为操作1 则输入两个人a b 对这两个人执行操作1
若为操作2 则输入两个人a b 询问这两个人是否认识
(1<=n,m<=10000)

Output

对于每一个操作二
若认识 输出Yes
否则输出No

Sample Input

2
4 5
1 1 2
1 3 4
1 1 3
2 1 4
2 2 4
6 3
1 1 2
1 3 4
2 1 3

Sample Output

Yes
Yes
No

思路：本题是并查集的模板题，并查集可以用来判断所属团体，或者分析条件冲突（典型的如食物链问题，真假话判断问题），具体的大家可以上网百度。

AC代码：

#include <stdio.h>
#include <iostream>
using namespace std;
const int maxn=10005;int par[maxn],_rank[maxn];void init(int n){for(int i=0;i<=n;i++){par[i]=i;_rank[i]=0;}
}int find(int x){if(par[x]==x){return x;}else{return par[x]=find(par[x]);} 
}void unite(int x,int y){x=find(x);y=find(y);if(x==y)return;if(_rank[x]<_rank[y]){par[x]=y;}else{par[y]=x;if(_rank[x]==_rank[y])_rank[x]++;}
}bool same(int x,int y){return find(x)==find(y);
}int main(){int T;scanf("%d",&T);while(T--){int n,m;scanf("%d %d",&n,&m);init(n);int a,b,c;for(int i=0;i<m;i++){cin>>a>>b>>c;if(a==1){unite(b,c);}else{if(same(b,c))printf("Yes\n");else printf("No\n");}}}return 0;
} 

转载于:.html