题解 | #并查集的实现#

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<stack>
using namespace std;
const int N = 1e6 + 7;
class UnionFindSets {
  public:
    int father[N];
    int n;
    UnionFindSets(int usize) {
        n = usize;
        for (int i = 0; i <= n; i++) {
            father[i] = i;
        }
    }
    int find(int i) {
        if (i != father[i]) {
            father[i] = find(father[i]);
            //i = father[i];
        }
        return father[i];
    }
    bool issame(int x, int y) {
        return find(x) == find(y);
    }
    void unionset(int x, int y) {
        father[find(x)] = find(y);
    }

};
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    UnionFindSets s(n);
    int opt, x, y;
    while (m--) {

        scanf("%d", &opt);

        if (opt == 1) {

            scanf("%d%d", &x, &y);
            if (s.issame(x, y)) {
                cout << "Yes" << endl;
            } else cout << "No" << endl;
        } else {
            scanf("%d%d", &x, &y);
            s.unionset(x, y);
        }

    }








    return 0;
}