【ACWing】1249. 亲戚

亲戚"/>

【ACWing】1249. 亲戚

题目地址：

/

或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱，判断两个人是否是亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情况下，最好的帮手就是计算机。为了将问题简化，你将得到一些亲戚关系的信息，如Marry和Tom是亲戚，Tom和Ben是亲戚，等等。从这些信息中，你可以推出Marry和Ben是亲戚。请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。

输入格式：
输入由两部分组成。
第一部分以 N , M N,M N,M开始。 N N N为问题涉及的人的个数。这些人的编号为 1 , 2 , 3 , … , N 1,2,3,…,N 1,2,3,…,N。下面有 M M M行，每行有两个数 a i , b i a_i,b_i ai​,bi​，表示已知 a i a_i ai​和 b i b_i bi​是亲戚。
第二部分以 Q Q Q开始。以下 Q Q Q行有 Q Q Q个询问，每行为 c i , d i c_i,d_i ci​,di​，表示询问 c i c_i ci​和 d i d_i di​是否为亲戚。

输出格式：
对于每个询问 c i , d i c_i,d_i ci​,di​，输出一行：若 c i c_i ci​和 d i d_i di​为亲戚，则输出“Yes”，否则输出“No”。

数据范围：
1 ≤ N ≤ 20000 1≤N≤20000 1≤N≤20000
1 ≤ M ≤ 1 0 6 1≤M≤10^6 1≤M≤106
1 ≤ Q ≤ 1 0 6 1≤Q≤10^6 1≤Q≤106

直接用并查集。代码如下：

#include <iostream>
using namespace std;const int N = 2e4 + 10;
int n, m, q;
int p[N];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;scanf("%d%d", &x, &y);p[find(x)] = find(y);}scanf("%d", &q);while (q--) {int x, y;scanf("%d%d", &x, &y);if (find(x) == find(y)) puts("Yes");else puts("No");}return 0;
}

时间复杂度 O ( n + ( m + q ) log ⁡ ∗ n ) O(n+(m+q)\log ^*n) O(n+(m+q)log∗n)，空间 O ( n ) O(n) O(n)。