并查集的实现

我以前也不会呀，自从用了并查集之后，嗨，效果还真好！我们全家都用它！——某大佬

关于并查集，有以下题型：

1. LeetCode130——Surrounded Regions——给了个二维 grid，把里面O全部变成X，但是边界和边界联通区域内的O保留（也能用DFS）
2. LeetCode261——Graph Valid Tree——给了N个结点和一个边的集合，问这个边的集合能不能构成一棵树
3. ...

并查集是一种树形数据结构，它由一个整型数组和两种操作组成：

1. 整型数组——记录每一个点对应前导点的下标
2. find——确定元素属于哪一个子集，可以使用它来确定两个元素是否属于同一个子集
3. union——将两个子集合并成一个集合

并查集的通用代码（看完你就明白这是个啥玩意儿了）：

class UnionFind {
public:
    UnionFind (int sz) {
        pre = vector<int>(sz);
        for (int i = 0; i < sz; ++i) { pre[i] = i; }
    }

    // 查找根节点
    int find(int x) {
        int root = x;
        while (pre[root] != root) {
            root = pre[root];
        }
        // 路径压缩（降低时间复杂度）
        int start = x;
        while(pre[start] != root) {
            int tmp = pre[start];
            pre[start] = root;
            start = tmp;
        }
        return root;
    }

    // 合并子集
    void join(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX != rootY) pre[rootY] = rootX;
    }

private:
    vector<int> pre;
};

图片如下：

基于上面👆并查集的框架，稍微修改一下，即可得到本题代码：

//
// Created by jt on 2020/9/7.
//
#include <vector>
#include <iostream>
using namespace std;

class UnionFind {
public:
    UnionFind (int sz) {
        pre = vector<int>(sz+1);
        for (int i = 1; i < sz; ++i) { pre[i] = i; }
    }

    // 查找根节点
    int find(int x) {
        int root = x;
        while (pre[root] != root) {
            root = pre[root];
        }
        // 路径压缩（降低时间复杂度）
        int start = x;
        while(pre[start] != root) {
            int tmp = pre[start];
            pre[start] = root;
            start = tmp;
        }
        return root;
    }

    bool isSameSet(int x, int y) {
        return find(x) == find(y);
    }

    // 合并子集
    void join(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX != rootY) pre[rootY] = rootX;
    }

private:
    vector<int> pre;
};

int main() {
    int N, M;
    cin >> N >> M;
    UnionFind uf(N);
    for (int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1) {
            if (uf.isSameSet(b, c)) cout << "Yes" << endl;
            else cout << "No" << endl;
        } else {
            uf.join(b, c);
        }
    }
}