并查集

推荐参考的题目:

https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths/

https://leetcode.cn/problems/maximum-number-of-points-from-grid-queries/

iota函数，用于赋予连续的值(Defined in header <numeric>)

查找

合并

是否连通

---

个人初步使用的并查集模板，没有加入权重，或者是统计集合的size，等之后做到这类更难的题目再附加

#include <vector>
#include <iostream>
#include <numeric>

using namespace std;

const int n= 1e5 + 7;

struct UnionFind {
    int fa[N];
    void build(int n){
        for (int i = 1; i <= n; i++) fa[i] = i; // 初始化1~n，可以用iota
    };
    int find (int x) {
        if (x != fa[x]) fa[x] = find(fa[x]);
        return fa[x];
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x != y) fa[x] = y;
    }
    bool is_connected(int x, int y) {
        x = find(x), y = find(y);
        return x == y;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    UnionFind uf;
    uf.build(n);
    while (m --) {
        char op;
        int a, b;
        cin >> op;
        scanf("%d %d", &a, &b);
        if (op == 'M') uf.unite(a, b);
        if (op == 'Q') {
            if(uf.is_connected(a, b)) {
                puts("Yes");
            }
            else puts("No");
        }
    }
    
    return 0;
}

带统计集合的size的板子

#include <vector>
#include <iostream>
#include <numeric>

using namespace std;

const int 1e5 + 7;

struct UnionFind {
	int fa[N], sz[N];
    void bulid(int n) {
        for (int i = 1; i <= n; i++) {
            fa[i] = i, sz[i] = 1;
        }
    }
    int find(int x) {
        if (x != fa[x]) fa[x] = find(fa[x]);
        return fa[x];
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x != y) {
            fa[x] = y;
            sz[y] += sz[x];
        }
    }
    bool is_connected(int x, int y) {
        x = find(x), y = find(y);
        return x == y;
    }
    int get_sz(int x) {
        x = find(x);
        return sz[x];
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    UnionFind uf(n + 1);
    
    while (m --) {
        char op[3];
        scanf("%s", op);
        if (op[0] == 'C') {
            int a, b;
            scanf("%d %d", &a, &b);
            uf.unite(a, b);
        }
        if (op[0] == 'Q') {
            if (op[1] == '1') {
                int a, b;
                scanf("%d %d", &a, &b);
                if (uf.is_connected(a, b)) {
                    puts("Yes");
                }
                else puts("No");
            }
            else if (op[1] == '2') {
                int a;
                scanf("%d", &a);
                printf("%d\n", uf.get_sz(a));
            }
        }
    }
    
    return 0;
}