NC200435. 找朋友
描述
——你要是愿意，我就永远存在
某人的朋友圈实在是过于庞大且复杂，要判断两个人是不是朋友，那还真不容易。
现给出某个朋友圈关系图，求任意给出的两个人是否是朋友。
规定：如果x和y是朋友，y和z是朋友，那么x和z也是朋友。
如果x和y是朋友，那么x的朋友都是y的朋友，y的朋友也都是x的朋友。
输入描述
第一行，三个整数n,m,p,(n ≤ 50000,m ≤ 50000,p≤50000)，分别表示有n个人，m个朋友关系，询问p对朋友关系。
以下m行：每行两个数Mi, Mj，1 ≤ Mi, Mj ≤ n，表示Mi和Mj具有朋友关系。
接下来p行：每行两个数Pi ,Pj,询问Pi，Pj是否具有盆友关系
输出描述
P行，每行一个“Yes”或“No”(不包含引号)。表示第i个询问的答案为“具有”或“不具有”朋友关系。
示例1
输入:
6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6
输出:
Yes Yes No
C(clang 3.9) 解法, 执行用时: 44ms, 内存消耗: 2280K, 提交时间: 2019-12-16 11:04:32
#include<stdio.h>
#define N 50001
int son[N];
int find(int x)
{
if(x==son[x]) return x;
else return son[x]=find(son[x]);
}
int main()
{
int i,n,m,p;
scanf("%d%d%d",&n,&m,&p);
for(i=1;i<=n;i++)
son[i]=i;
for(i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
son[find(a)]=find(b);
}
for(i=1;i<=p;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(find(a)==find(b)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 151ms, 内存消耗: 1364K, 提交时间: 2020-05-22 19:09:36
#include<iostream>
using namespace std;
int f[100000];
int find(int k){
if (f[k]==k) return k;
return f[k]=find(f[k]);
}
int n,m;
int q,a,b;
int main(){
cin>>n>>m>>q;
for (int i=1;i<=n;i++){
f[i]=i;
}
for (int i=0;i<m;i++){
cin>>a>>b;
f[find(a)]=find(b);
}
for (int i=0;i<q;i++){
cin>>a>>b;
if (find(a)==find(b)){
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
}
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 115ms, 内存消耗: 868K, 提交时间: 2019-12-15 14:15:23
#include<bits/stdc++.h>
using namespace std;
int n,m,p,f[50001],x,y;
int find(int d)
{
if(f[d]==d) return d;
f[d]=find(f[d]);
return f[d];
}
int main()
{
cin>>n>>m>>p;
for(int i=1;i<=n;++i) f[i]=i;
for(int i=1;i<=m;++i)
{
cin>>x>>y;
x=find(x);
f[find(y)]=x;
}
for(int i=1;i<=p;++i)
{
cin>>x>>y;
if(find(x)==find(y)) printf("Yes\n");
else printf("No\n");
}
}