题目:https://www.luogu.com.cn/problem/P1551
知识点:
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#define SIZE 10005
using namespace std;
int read(){
int x = 0, f =1;
char c = getchar();
while (c<'0'||c>'9') {
if (c=='-') {
f = -1;
}
c = getchar();
}
while (c>='0'&&c<='9') {
x = x*10 + c - '0';
c = getchar();
}
return x*f;
}
int f[SIZE];
int FindDad(int x)//找出x家的大佬 也就是二叉树的祖先节点
{
if(f[x]==x)//x是x的爸爸,简单的来说就是x没爸爸了
//他是家里最大的大佬,所以返回的x就是我们所求的祖先节点
return x;
return f[x] = FindDad(f[x]);//x不是他自己的爸爸,所以他上面还
//有爸爸,我们的目标是祖先节点,所以我们此时要做的是问他
//爸爸的爸爸是谁,即再使用一次fd(find)函数【其实就是一个递归过程
}
void Link(int x,int y)
{
f[FindDad(y)]=FindDad(x);//合并x子集和y子集,直接把x子集的祖先节
//点与y子集的祖先节点连接起来,通俗点来说就是把x的最大祖
//先变成y子集最大祖先的爸爸
}
int main(){
int n = read(), m = read(),p = read();
for (int i = 1; i<=n; i++) {
f[i] = i;
}
for (int i = 0; i<m; i++) {
int Mi = read(),Mj = read();
Link(Mi, Mj);
}
for (int i = 0; i<p; i++) {
int Pi = read(),Pj = read();
if (FindDad(Pi)==FindDad(Pj)) {
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}
return 0;
}
网友评论