家族查询

题目描述
某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。（人数≤5000，询问亲戚关系次数≤5000）。

输入描述
第一行为数据组数T(T <= 20)
对于每组数据，第一行有两个整数n、m(1 <= n, m <= 5000)，表示有n个人，编号1~n，其中存在m个亲戚关系
接下来m行，每行有两个整数u、v(u != v, 1 <= u, v <= n)，表示u和v之间有亲戚关系
然后是询问组数q(1 <= q <= 5000)
接下来q行，每行有两个整数u、v(u != v, 1 <= u, v <= n)，询问u和v之间是否有亲戚关系

输出描述
对于每组数据，输出q行，每行为"Yes"或"No"，表示是否存在亲戚关系
每组数据的输出用空行隔开

输入样例

2
3 1
2 3
2
1 2
2 3
4 2
1 2
1 4
3
1 2
1 3
2 4

输出样例

No
Yes

Yes
No
Yes

参考答案

#include <iostream>
using namespace std;
const int maxn = 10000;
int p[maxn];

int find(int x)
{
    //查找过程顺带进行了路径压缩
    return (x == p[x]) ? x : (p[x] = find(p[x]));
}

void merge(int x, int y)
{
    p[y] = x;
}

int main()
{
    int T; //数据组数
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        int n, m;
        cin >> n >> m;
        for (int j = 1; j <= n; j++)
        {
            p[j] = j;
        }
        int u, v;
        for (int j = 0; j < m; j++)
        {
            cin >> u >> v;
            merge(find(u), find(v));
        }
        int q;
        cin >> q;
        for (int j = 0; j < q; j++)
        {
            cin >> u >> v;
            if (find(u) == find(v))
            {
                cout << "Yes" << endl;
            }
            else
            {
                cout << "No" << endl;
            }
        }
        cout << endl;
    }
}