并查集模板

#include <iostream>
#include <vector>

using namespace std;

class UF {
private:
    vector<int> parent; // 记录父节点
    vector<int> rank; // 记录树的深度
    int count; // 连通分量数量

public:
    UF(int N)
        : parent(N + 1)
        , rank(N + 1, 1)
        , count(N)
    {
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
    }

    int countN() { return count; }

    long long find(long long p)
    {
        while (parent[p] != p) {
            parent[p] = parent[parent[p]]; // 路径压缩
            p = parent[p];
        }
        return p;
    }

    void unionpq(int p, int q)
    {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;

        // 按秩合并（小树挂到大树上）
        if (rank[rootP] > rank[rootQ]) {
            parent[rootQ] = rootP;
        } else if (rank[rootP] < rank[rootQ]) {
            parent[rootP] = rootQ;
        } else {
            parent[rootQ] = rootP;
            rank[rootP]++;
        }
        count--;
    }

    bool connected(int p, int q)
    {
        return find(p) == find(q);
    }
};

int main()
{
    int N, M;
    cin >> N >> M;
    UF uf(N);
    for (int i = 0; i < M; i++) {
        int z, x, y;
        cin >> z >> x >> y;
        if (z == 1) {
            uf.unionpq(x, y);
        } else {
            if (uf.connected(x, y)) {
                cout << "Y" << endl;
            } else {
                cout << "N" << endl;
            }
        }
    }
}