思路与算法

初始化每个人为单独集合。先读N、M和M对亲戚，把每一对所在集合合并。所有关系读完后才读取Q及Q对询问；两人最终代表元相同则输出Yes，否则No。使用按集合大小合并和迭代路径压缩，提高百万关系与百万询问下的效率。

正确性说明

初始只有本人之间的关系。每次合并一对亲戚所在集合，把所有可经这条新关系互相到达的人放在同一集合，恰好维护已知关系图的连通分量。由于亲戚关系对称且传递，处理完全部关系后，连通分量就是完整亲戚等价类。因此两个代表元相同当且仅当为亲戚，询问答案准确。

复杂度

初始化O(N)，按大小合并加路径压缩的M次合并与Q次查询摊还O((M+Q)*alpha(N))，总时间O(N+(M+Q)*alpha(N))，并查集空间O(N)。输入和答案流式处理，不保存百万对关系或查询。N<=20000，M和Q均可达1000000。

易错点

本源第一行只有N、M，Q在M对关系之后读取；不能直接复用第一行N、M、Q且均<=5000的J00242协议。重复关系、自身关系不影响等价类；任何人与自己是亲戚。输出为Yes和No，首字母大写。覆盖完整百万规模，独立答案用整图DFS连通分量核对。

参考代码（C++11）

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
struct DSU {
    vector<int> p, size;
    DSU(int n) : p(n + 1), size(n + 1, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        int r = x;
        while (p[r] != r)
            r = p[r];
        while (p[x] != x) {
            int y = p[x];
            p[x] = r;
            x = y;
        }
        return r;
    }
    void join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return;
        if (size[a] < size[b])
            swap(a, b);
        p[b] = a;
        size[a] += size[b];
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    DSU d(n);
    while (m--) {
        int a, b;
        cin >> a >> b;
        d.join(a, b);
    }
    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << (d.find(a) == d.find(b) ? "Yes\n" : "No\n");
    }
}