【算法入门-21】生成树与并查集

• 课件
  • 生成树与并查集.pdf
  • 这周的作业先不用做，我们后面还会再讲

• B 站学习视频：

  • 1、并查集 - 基本操作, 路径压缩, 按秩合并

• 并查集模板（如果你不想写这么长，请自己修改）

// 并查集(Union-Find Disjoint Sets/DSU)
struct DSU {
    int n;
    vector<int> f, sz;

    DSU(int N): n(N) {
        // 将 f 的 size 设置为 n + 1
        f.resize(n + 1);

        // 相当于 for (int i = 0; i <= n; i++) f[i] = i;
        // 将从 0 开始的一段连续的数赋值给 f.begin() 到 f.end()
        iota(f.begin(), f.end(), 0);

        // 将 sz 的 size 设置为 n + 1, 并初始化为 1
        sz.assign(n + 1, 1);

        // 对于 vector 的初始化
        // 如果只需要设置 size, 不需要设置初值, 用 resize
        // 如果既需要设置 size, 也需要设置初值, 用 assign
    }

    // 路径压缩
    int find(int x) {
        return f[x] == x ? f[x] : f[x] = find(f[x]);
    }

    // 判断 x, y 是否在同一集合
    bool same(int x, int y) {
        return find(x) == find(y);
    }

    // 启发式合并
    int merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return x;
      
        // 将 sz小的 合并到 sz大的
        if (sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y], f[y] = x;
      
        return x;
    }

    // 返回 x 所在的集合的大小
    int size(int x) {
        return sz[find(x)];
    }
};