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

关于并查集,有以下题型:

  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);
        }
    }
}