【蓝桥杯集训·每日一题】AcWing 1249. 亲戚

一、题目

1、原题链接

1249. 亲戚

2、题目描述

或许你并不知道，你的某个朋友是你的亲戚。

他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。

如果能得到完整的家谱，判断两个人是否是亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。

在这种情况下，最好的帮手就是计算机。

为了将问题简化，你将得到一些亲戚关系的信息，如Marry和Tom是亲戚，Tom和Ben是亲戚，等等。

从这些信息中，你可以推出Marry和Ben是亲戚。

请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。

输入格式

输入由两部分组成。

第一部分以 N,M 开始。N 为问题涉及的人的个数。这些人的编号为 1,2,3,…,N。下面有 M 行，每行有两个数 ai,bi，表示已知
ai 和 bi 是亲戚。

第二部分以 Q 开始。以下 Q 行有 Q 个询问，每行为 ci,di ，表示询问 ci 和 di 是否为亲戚。

输出格式

对于每个询问 ci,di，输出一行：若 ci 和 di 为亲戚，则输出Yes，否则输出No。

数据范围

1≤N≤20000,1≤M≤10⁶,1≤Q≤10⁶

输入样例：

10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9
1
2
3
4
5
6
7
8
9
10
11
12

输出样例：

Yes
No
Yes
1
2
3

二、解题报告

1、思路分析

（1）利用并查集，将所有互为亲戚的合并为同一个集合。
（2）通过查找两个结点的祖宗结点是否相同来判断两人是否为亲戚。
（3）并查集模板题，注意细节，并且此题使用cin、cout会超时，应使用scanf、printf或puts进行输入输出。

2、时间复杂度

时间复杂度为O(n)

3、代码详解

#include <iostream>
using namespace std;
const int N=20010;
int n,m;
int p[N];    //p[]存储每个结点的祖宗结点
//查找操作，返回x的祖宗结点
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);   //如果p[x]不是祖宗的话，递归查找x的祖宗
    return p[x];                   //直到找到x的祖宗，返回
}
int main(){
    scanf("%d%d",&n,&m);     //使用cin、cout会TLE
    //初始化，每个结点的祖宗为自身
    for(int i=1;i<=n;i++){
        p[i]=i;
    }
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        if(find(a)==find(b)) continue;
        p[find(b)]=find(a);   //a,b的祖宗结点不同，则合并
    }
    int q;
    cin>>q;
    while(q--){
        int c,d;
        scanf("%d%d",&c,&d);
        if(find(c)==find(d)) puts("Yes");   //祖宗相同输出Yes，否则输出No
        else puts("No");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

三、知识风暴

并查集

• 并查集主要用于处理一些不相交集合的合并问题。
• 具体操作可以参考我的这篇博客点击这里的“知识风暴”模块。