Motion Rule (16)-Union Check Basic Questions-Relations

亲戚(Relations)

或许你并不知道,你的某个朋友是你的亲戚.He may be the grandson of your great-grandfather's grandfather's son-in-law's nephew's cousin's grandson.如果能得到完整的家谱,It should be feasible to judge whether two people are relatives,但如果两个人的最近公共祖先与他们相隔好几代,使得家谱十分庞大,那么检验亲戚关系实非人力所能及.在这种情况下,最好的帮手就是计算机.

为了将问题简化,你将得到一些亲戚关系的信息,如同Marry和Tom是亲戚,Tom和Ben是亲戚,等等.从这些信息中,你可以推出Marry和Ben是亲戚.请写一个程序,Questions for our concerned relatives,以最快的速度给出答案.

Reference input and output format输入由两部分组成.

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

第二部分以Q开始.以下Q行有Q个询问(1 ≤ Q ≤ 1 000 000),每行为ci, di,表示询问ci和di是否为亲戚.

对于每个询问ci, di,若ci和di为亲戚,则输出Yes,否则输出No.

样例输入与输出

输入

10 7

2 4

5 7

1 3

8 9

1 2

5 6

2 3

3

3 4

7 10

8 9

输出

Yes

No

Yes

#include <cstdio>
#include <iostream>
using namespace std;
int fa[20001], n, m, x, y, r1, r2;
int find(int u)
{
    return fa[u] == u ? u : fa[u] = find(fa[u]);
}
int read()
{
    int x = 0;
    char ch = getchar();
    while (!isdigit(ch))
        ch = getchar();
    while (isdigit(ch))
        x = x * 10 + ch - 48, ch = getchar();
    return x;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++)
    {
        x = read();
        y = read();
        r1 = find(x);
        r2 = find(y);
        if (r1 != r2)
            fa[r1] = r2;
    }
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        x = read();
        y = read();
        r1 = find(x);
        r2 = find(y);
        if (r1 == r2)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}