top1编程
← 返回题目
题解

【入门】是不是亲戚

1 条题解

  • 0
    @ 2026-7-29 0:18:15
    #include <iostream>
    #include <vector>
    using namespace std;
    
    class UnionFind {
    private:
        vector<int> parent;
    
    public:
        UnionFind(int n) {
            parent.resize(n + 1); // 1-indexed
            for (int i = 1; i <= n; i++) {
                parent[i] = i;
            }
        }
    
        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]); // 路径压缩
            }
            return parent[x];
        }
    
        void unite(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                parent[rootX] = rootY;
            }
        }
    
        bool isConnected(int x, int y) {
            return find(x) == find(y);
        }
    };
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        int n, m, p;
        cin >> n >> m >> p;
    
        UnionFind uf(n);
    
        // 构建亲戚关系
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            uf.unite(a, b);
        }
    
        // 处理询问
        for (int i = 0; i < p; i++) {
            int u, v;
            cin >> u >> v;
            if (uf.isConnected(u, v)) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }
    
        return 0;
    }
    
    • 1