NC215094. 朋友
描述
输入描述
第一行包含两个整数 N,M ,表示共有 N 个同学和 M 个操作并且满足 x + y = M
接下来 M 行，每行包含三个整数 Zi, Ai, Bi
当 Zi=1，表示 Ai 和 Bi 是好朋友
当 Zi=2，输出 Ai 和 Bi 是否是好朋友，是的输出 Y ，否则输出 N
输出描述
对于每一个 Zi=2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N
示例1
输入:
10 20 1 4 8 1 1 2 1 7 2 2 6 8 1 3 2 2 9 5 1 7 1 2 9 10 1 1 5 2 1 9 1 4 8 2 7 9 2 9 1 2 9 6 2 10 8 1 3 5 1 6 10 1 4 8 2 5 4 1 8 4
输出:
N N N N N N N N N
C++(clang++11) 解法, 执行用时: 59ms, 内存消耗: 2924K, 提交时间: 2021-01-31 20:18:34
#include<iostream>
using namespace std;
const int N=1000010;
int p[N],n,m;
int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
p[i]=i;
while(m--){
int x,y,z;
scanf("%d%d%d",&z,&x,&y);
if(z==1){
if(find(x)!=find(y))
p[find(x)]=p[y];
}
else{
if(find(x)==find(y))
printf("Y\n");
else
printf("N\n");
}
}
}