1
并查集用"森林"表示——每棵树是一个集合, 根节点是代表元素
2

3
初始 (每个元素自成一棵树):
4
  0   1   2   3   4   5   6   7
5

6
Union(0,1): 1 的 parent = 0
7
  0   2   3   4   5   6   7
8
  |
9
  1
10

11
Union(2,3): 3 的 parent = 2
12
  0   2   4   5   6   7
13
  |   |
14
  1   3
15

16
Union(0,2): 2 的 parent = 0  (把 2 的树挂到 0 下面)
17
    0       4   5   6   7
18
   / \
19
  1   2
20
      |
21
      3
22

23
Union(4,5), Union(6,7), Union(4,6):
24
    0           4
25
   / \         / \
26
  1   2       5   6
27
      |           |
28
      3           7
29

30
现在: Find(3) → 走 3→2→0 → 返回 0
31
      Find(7) → 走 7→6→4 → 返回 4
32
      Connected(1, 3) → Find(1)==0, Find(3)==0 → true ✅
33
      Connected(1, 7) → Find(1)==0, Find(7)==4 → false ❌

1
class QuickFind {
2
    std::vector<int> _id;  // _id[i] = i 所在集合的标识
3

4
public:
5
    QuickFind(int n) : _id(n) {
6
        std::iota(_id.begin(), _id.end(), 0);
7
    }
8

9
    int find(int x) const { return _id[x]; }  // O(1)!
10

11
    void unite(int x, int y) {
12
        int id_x = _id[x], id_y = _id[y];
13
        if (id_x == id_y) return;
14

15
        // 把所有 id_y 的元素改成 id_x → O(n)!
16
        for (int& id : _id) {
17
            if (id == id_y) id = id_x;
18
        }
19
    }
20

21
    bool connected(int x, int y) const { return _id[x] == _id[y]; }
22
};

1
class QuickUnion {
2
    std::vector<int> _parent;
3

4
public:
5
    QuickUnion(int n) : _parent(n) {
6
        std::iota(_parent.begin(), _parent.end(), 0);  // parent[i] = i
7
    }
8

9
    int find(int x) {
10
        while (_parent[x] != x) {
11
            x = _parent[x];  // 沿着 parent 走到根
12
        }
13
        return x;
14
    }
15

16
    void unite(int x, int y) {
17
        int rx = find(x), ry = find(y);
18
        if (rx != ry) {
19
            _parent[ry] = rx;  // 把 y 的根挂到 x 的根下面
20
        }
21
    }
22

23
    bool connected(int x, int y) { return find(x) == find(y); }
24
};

1
// 路径压缩 —— 递归版 (最简洁)
2
int find(int x) {
3
    if (_parent[x] != x) {
4
        _parent[x] = find(_parent[x]);  // 递归 + 直接挂到根
5
    }
6
    return _parent[x];
7
}
8

9
// 路径压缩 —— 迭代版 (防栈溢出)
10
int find_iterative(int x) {
11
    int root = x;
12
    while (_parent[root] != root) {
13
        root = _parent[root];
14
    }
15
    // 第二遍: 把路径上所有节点直接指向根
16
    while (_parent[x] != root) {
17
        int next = _parent[x];
18
        _parent[x] = root;
19
        x = next;
20
    }
21
    return root;
22
}
23

24
// 路径压缩的"兄弟版" —— 路径分裂 (Path Splitting)
25
// 每个节点指向祖父节点 (不需要两遍, 效果接近完全压缩)
26
int find_splitting(int x) {
27
    while (_parent[x] != x) {
28
        _parent[x] = _parent[_parent[x]];  // 指向祖父
29
        x = _parent[x];
30
    }
31
    return x;
32
}

1
#include <vector>
2
#include <numeric>
3

4
class UnionFind {
5
    std::vector<int> _parent;
6
    std::vector<int> _rank;
7
    int _count;  // 连通分量数
8

9
public:
10
    UnionFind(int n) : _parent(n), _rank(n, 0), _count(n) {
11
        std::iota(_parent.begin(), _parent.end(), 0);
12
    }
13

14
    // ========== Find (路径压缩) ==========
15
    int find(int x) {
16
        if (_parent[x] != x) {
17
            _parent[x] = find(_parent[x]);  // 路径压缩
18
        }
19
        return _parent[x];
20
    }
21

22
    // ========== Union (按秩合并) ==========
23
    bool unite(int x, int y) {
24
        int rx = find(x), ry = find(y);
25
        if (rx == ry) return false;  // 已在同一集合
26

27
        // 按秩合并: 矮树挂到高树下
28
        if (_rank[rx] < _rank[ry]) std::swap(rx, ry);
29
        _parent[ry] = rx;
30

31
        // 如果高度相同, 合并后高度 +1
32
        if (_rank[rx] == _rank[ry]) ++_rank[rx];
33

34
        --_count;  // 连通分量减少
35
        return true;
36
    }
37

38
    // ========== 查询 ==========
39
    bool connected(int x, int y) { return find(x) == find(y); }
40
    int count() const { return _count; }  // 当前连通分量数
41
};

1
class UnionFindBySize {
2
    std::vector<int> _parent;
3
    std::vector<int> _size;
4
    int _count;
5

6
public:
7
    UnionFindBySize(int n) : _parent(n), _size(n, 1), _count(n) {
8
        std::iota(_parent.begin(), _parent.end(), 0);
9
    }
10

11
    int find(int x) {
12
        if (_parent[x] != x) _parent[x] = find(_parent[x]);
13
        return _parent[x];
14
    }
15

16
    bool unite(int x, int y) {
17
        int rx = find(x), ry = find(y);
18
        if (rx == ry) return false;
19

20
        // 小集合挂到大集合下
21
        if (_size[rx] < _size[ry]) std::swap(rx, ry);
22
        _parent[ry] = rx;
23
        _size[rx] += _size[ry];  // 更新大小
24

25
        --_count;
26
        return true;
27
    }
28

29
    int size_of(int x) { return _size[find(x)]; }
30
    bool connected(int x, int y) { return find(x) == find(y); }
31
    int count() const { return _count; }
32
};

1
初始：unite(a, b, 2.0) → a/b=2, 即 weight(a→b)=2.0
2

3
    b (root)
4
    ↑ w=2.0
5
    a
6

7
再 unite(b, c, 3.0) → b/c=3, 即 weight(b→c)=3.0
8

9
    c (root)
10
    ↑ w=3.0
11
    b
12
    ↑ w=2.0
13
    a
14

15
现在 find(a) 触发路径压缩:
16
  Step 1: 递归 find(b)
17
    Step 1.1: 递归 find(c)
18
      c 是根, 返回 c
19
    Step 1.2: 回到 b
20
      weight[b] *= weight[parent[b]] → weight[b] = 3.0 × 1.0 = 3.0
21
      parent[b] = c  (已经是 c, 不变)
22
  Step 2: 回到 a
23
    weight[a] *= weight[parent[a]] → weight[a] = 2.0 × 3.0 = 6.0
24
    parent[a] = c  (直接指向根!)
25

26
压缩后:
27
    c (root)
28
   ↗ ↑
29
  a   b
30
  w=6 w=3
31

32
query(a, c) = weight[a] / weight[c] = 6.0 / 1.0 = 6.0 ✅
33
query(a, b) = weight[a] / weight[b] = 6.0 / 3.0 = 2.0 ✅

1
已有:
2
  a --w[a]--> root_x    (a 到 root_x 的累积权重 = w[a])
3
  b --w[b]--> root_y    (b 到 root_y 的累积权重 = w[b])
4

5
现在 unite(a, b, val), 即 a/b = val:
6
  需要让 root_x 和 root_y 合并
7

8
  假设 root_y 挂到 root_x 下:
9
    weight[root_y] = ?
10

11
  推导:
12
    a = w[a] × root_x
13
    b = w[b] × root_y
14
    a/b = val  →  w[a] × root_x / (w[b] × root_y) = val
15
    →  root_y = w[a] × root_x / (val × w[b])
16
    →  weight[root_y → root_x] = w[a] / (val × w[b])

1
class WeightedUnionFind {
2
    std::vector<int> _parent;
3
    std::vector<double> _weight;  // weight[i] = i 到 parent[i] 的权重比
4
    std::vector<int> _rank;
5

6
public:
7
    WeightedUnionFind(int n)
8
        : _parent(n), _weight(n, 1.0), _rank(n, 0)
9
    {
10
        std::iota(_parent.begin(), _parent.end(), 0);
11
    }
12

13
    // 带权路径压缩
14
    int find(int x) {
15
        if (_parent[x] != x) {
16
            int root = find(_parent[x]);
17
            _weight[x] *= _weight[_parent[x]];  // 权重累积!
18
            _parent[x] = root;
19
        }
20
        return _parent[x];
21
    }
22

23
    // 带权合并: x / y = value → x = value × y
24
    void unite(int x, int y, double value) {
25
        int rx = find(x), ry = find(y);
26
        if (rx == ry) return;
27

28
        if (_rank[rx] < _rank[ry]) {
29
            _parent[rx] = ry;
30
            _weight[rx] = value * _weight[y] / _weight[x];
31
        } else {
32
            _parent[ry] = rx;
33
            _weight[ry] = _weight[x] / (value * _weight[y]);
34
            if (_rank[rx] == _rank[ry]) ++_rank[rx];
35
        }
36
    }
37

38
    // 查询 x / y 的值; 如果不在同一集合返回 -1.0
39
    double query(int x, int y) {
40
        if (find(x) != find(y)) return -1.0;
41
        return _weight[x] / _weight[y];
42
    }
43
};

1
// 维护每个集合的额外信息
2
class EnhancedUnionFind {
3
    std::vector<int> _parent, _rank;
4
    std::vector<int> _size;      // 集合大小
5
    std::vector<int> _min_val;   // 集合中最小值
6
    std::vector<int> _max_val;   // 集合中最大值
7

8
public:
9
    EnhancedUnionFind(int n, const std::vector<int>& values)
10
        : _parent(n), _rank(n, 0), _size(n, 1),
11
          _min_val(values), _max_val(values)
12
    {
13
        std::iota(_parent.begin(), _parent.end(), 0);
14
    }
15

16
    int find(int x) {
17
        if (_parent[x] != x) _parent[x] = find(_parent[x]);
18
        return _parent[x];
19
    }
20

21
    void unite(int x, int y) {
22
        int rx = find(x), ry = find(y);
23
        if (rx == ry) return;
24

25
        if (_rank[rx] < _rank[ry]) std::swap(rx, ry);
26
        _parent[ry] = rx;
27

28
        // 合并额外信息
29
        _size[rx] += _size[ry];
30
        _min_val[rx] = std::min(_min_val[rx], _min_val[ry]);
31
        _max_val[rx] = std::max(_max_val[rx], _max_val[ry]);
32

33
        if (_rank[rx] == _rank[ry]) ++_rank[rx];
34
    }
35

36
    int get_size(int x) { return _size[find(x)]; }
37
    int get_min(int x) { return _min_val[find(x)]; }
38
    int get_max(int x) { return _max_val[find(x)]; }
39
};

1
std::vector<std::vector<std::string>> accountsMerge(
2
    std::vector<std::vector<std::string>>& accounts)
3
{
4
    // 邮箱 → 编号
5
    std::unordered_map<std::string, int> email_id;
6
    std::unordered_map<std::string, std::string> email_name;
7
    int id = 0;
8

9
    for (auto& acc : accounts) {
10
        const std::string& name = acc[0];
11
        for (int i = 1; i < static_cast<int>(acc.size()); ++i) {
12
            if (email_id.find(acc[i]) == email_id.end()) {
13
                email_id[acc[i]] = id++;
14
            }
15
            email_name[acc[i]] = name;
16
        }
17
    }
18

19
    // 并查集: 同一账户内的邮箱 Union
20
    UnionFind uf(id);
21
    for (auto& acc : accounts) {
22
        int first = email_id[acc[1]];
23
        for (int i = 2; i < static_cast<int>(acc.size()); ++i) {
24
            uf.unite(first, email_id[acc[i]]);
25
        }
26
    }
27

28
    // 按根节点分组
29
    std::unordered_map<int, std::set<std::string>> groups;
30
    for (auto& [email, eid] : email_id) {
31
        groups[uf.find(eid)].insert(email);
32
    }
33

34
    // 组装结果
35
    std::vector<std::vector<std::string>> result;
36
    for (auto& [root, emails] : groups) {
37
        std::vector<std::string> merged;
38
        // 找这组任意一个邮箱的姓名
39
        merged.push_back(email_name[*emails.begin()]);
40
        for (auto& e : emails) {
41
            merged.push_back(e);
42
        }
43
        result.push_back(std::move(merged));
44
    }
45

46
    return result;
47
}
48
// 时间 O(n × m × α(n×m)), 空间 O(n × m)
49
// n = 账户数, m = 平均每个账户的邮箱数

1
bool equationsPossible(std::vector<std::string>& equations) {
2
    UnionFind uf(26);  // 26 个字母
3

4
    // 第一遍: 处理所有 == (合并)
5
    for (auto& eq : equations) {
6
        if (eq[1] == '=') {
7
            uf.unite(eq[0] - 'a', eq[3] - 'a');
8
        }
9
    }
10

11
    // 第二遍: 检查所有 != (是否矛盾)
12
    for (auto& eq : equations) {
13
        if (eq[1] == '!') {
14
            if (uf.connected(eq[0] - 'a', eq[3] - 'a')) {
15
                return false;  // a==b 但要求 a!=b → 矛盾!
16
            }
17
        }
18
    }
19

20
    return true;
21
}
22
// 时间 O(n × α(26)) ≈ O(n), 空间 O(1)

1
int longestConsecutive(std::vector<int>& nums) {
2
    std::unordered_map<int, int> num_to_id;
3
    int n = nums.size();
4
    if (n == 0) return 0;
5

6
    // 去重并分配 ID
7
    int id = 0;
8
    for (int num : nums) {
9
        if (num_to_id.find(num) == num_to_id.end()) {
10
            num_to_id[num] = id++;
11
        }
12
    }
13

14
    UnionFindBySize uf(id);
15

16
    // 对每个数, 如果 num+1 存在, Union 它们
17
    for (auto& [num, nid] : num_to_id) {
18
        if (num_to_id.count(num + 1)) {
19
            uf.unite(nid, num_to_id[num + 1]);
20
        }
21
    }
22

23
    // 找最大集合
24
    int max_size = 1;
25
    for (auto& [num, nid] : num_to_id) {
26
        max_size = std::max(max_size, uf.size_of(nid));
27
    }
28

29
    return max_size;
30
}
31
// 时间 O(n), 空间 O(n)

1
int numIslands(std::vector<std::vector<char>>& grid) {
2
    int m = grid.size(), n = grid[0].size();
3
    UnionFind uf(m * n);
4
    int water = 0;
5

6
    for (int i = 0; i < m; ++i) {
7
        for (int j = 0; j < n; ++j) {
8
            if (grid[i][j] == '0') {
9
                ++water;
10
                continue;
11
            }
12

13
            // 只向右和向下合并 (避免重复)
14
            if (i + 1 < m && grid[i + 1][j] == '1') {
15
                uf.unite(i * n + j, (i + 1) * n + j);
16
            }
17
            if (j + 1 < n && grid[i][j + 1] == '1') {
18
                uf.unite(i * n + j, i * n + j + 1);
19
            }
20
        }
21
    }
22

23
    return uf.count() - water;  // 总分量 - 水的个数 = 岛屿数
24
}
25
// 时间 O(m×n × α(m×n)), 空间 O(m×n)

1
std::vector<double> calcEquation(
2
    std::vector<std::vector<std::string>>& equations,
3
    std::vector<double>& values,
4
    std::vector<std::vector<std::string>>& queries)
5
{
6
    // 字符串 → 编号
7
    std::unordered_map<std::string, int> var_id;
8
    int id = 0;
9
    for (auto& eq : equations) {
10
        if (!var_id.count(eq[0])) var_id[eq[0]] = id++;
11
        if (!var_id.count(eq[1])) var_id[eq[1]] = id++;
12
    }
13

14
    WeightedUnionFind uf(id);
15

16
    // 建立关系: eq[0] / eq[1] = values[i]
17
    for (int i = 0; i < static_cast<int>(equations.size()); ++i) {
18
        uf.unite(var_id[equations[i][0]], var_id[equations[i][1]], values[i]);
19
    }
20

21
    // 查询
22
    std::vector<double> result;
23
    for (auto& q : queries) {
24
        if (!var_id.count(q[0]) || !var_id.count(q[1])) {
25
            result.push_back(-1.0);
26
        } else {
27
            result.push_back(uf.query(var_id[q[0]], var_id[q[1]]));
28
        }
29
    }
30

31
    return result;
32
}

1
Step 1: 与 LC 684 的区别
2
  LC 684 是无向图, 直接并查集判环即可。
3
  LC 685 是有向图, 多了一条边可能造成:
4
    Case A: 某个节点有 2 个父节点 (入度=2), 无环
5
    Case B: 某个节点有 2 个父节点 (入度=2), 且形成环
6
    Case C: 没有入度=2 的节点, 但有环 (环上某条是多余的)
7

8
Step 2: 观察
9
  树的性质: 除根外每个节点恰好 1 个父节点 (入度=1)
10
  多一条边 → 要么某节点入度变 2, 要么形成环
11

12
Step 3: 方案
13
  1. 先扫描所有边, 找入度=2 的节点 (如果有)
14
     → 记录指向它的两条边: candidate1 (先出现) 和 candidate2 (后出现)
15
  2. 先尝试删 candidate2 (题目要求返回最后出现的)
16
     → 用并查集加剩余边, 如果无环 → candidate2 就是答案
17
     → 如果有环 → 说明 candidate2 不是多余的, candidate1 是答案
18
  3. 如果没有入度=2 的节点 → Case C
19
     → 直接并查集判环 (和 LC 684 一样)

1
std::vector<int> findRedundantDirectedConnection(
2
    std::vector<std::vector<int>>& edges)
3
{
4
    int n = edges.size();
5
    std::vector<int> parent(n + 1, 0);  // parent[i] = i 的父节点
6

7
    // Step 1: 找入度=2 的节点
8
    std::vector<int> cand1, cand2;
9
    for (auto& e : edges) {
10
        if (parent[e[1]] == 0) {
11
            parent[e[1]] = e[0];  // 记录父节点
12
        } else {
13
            // e[1] 已有父节点 → 入度=2!
14
            cand1 = {parent[e[1]], e[1]};  // 先出现的边
15
            cand2 = e;                      // 后出现的边
16
        }
17
    }
18

19
    // 重建并查集
20
    std::iota(parent.begin(), parent.end(), 0);
21

22
    auto find = [&](int x) {
23
        while (parent[x] != x) {
24
            parent[x] = parent[parent[x]];  // 路径压缩
25
            x = parent[x];
26
        }
27
        return x;
28
    };
29

30
    for (auto& e : edges) {
31
        if (e == cand2) continue;  // 先尝试删 cand2
32

33
        int rx = find(e[0]), ry = find(e[1]);
34
        if (rx == ry) {
35
            // 有环!
36
            // 如果有 cand1 → cand2 不是问题, cand1 才是
37
            // 如果没有 cand1 → 这条边是多余的 (Case C)
38
            return cand1.empty() ? e : cand1;
39
        }
40
        parent[ry] = rx;
41
    }
42

43
    // 删 cand2 后无环 → cand2 就是多余的
44
    return cand2;
45
}
46
// 时间 O(n × α(n)), 空间 O(n)

1
// Roguelike 地图生成后, 需要验证所有房间是否连通
2
// 如果不连通, 要添加额外走廊
3

4
class MapConnectivityChecker {
5
    int _rows, _cols;
6
    UnionFind _uf;
7

8
    int _encode(int x, int y) const { return x * _cols + y; }
9

10
public:
11
    MapConnectivityChecker(int rows, int cols)
12
        : _rows(rows), _cols(cols), _uf(rows * cols) {}
13

14
    // 连接两个相邻的可通行格子
15
    void connect(int x1, int y1, int x2, int y2) {
16
        _uf.unite(_encode(x1, y1), _encode(x2, y2));
17
    }
18

19
    // 扫描地图, 合并所有相邻的可通行格子
20
    void scan_map(const std::vector<std::vector<int>>& map) {
21
        for (int i = 0; i < _rows; ++i) {
22
            for (int j = 0; j < _cols; ++j) {
23
                if (map[i][j] == 0) continue;  // 墙壁
24

25
                if (i + 1 < _rows && map[i + 1][j])
26
                    _uf.unite(_encode(i, j), _encode(i + 1, j));
27
                if (j + 1 < _cols && map[i][j + 1])
28
                    _uf.unite(_encode(i, j), _encode(i, j + 1));
29
            }
30
        }
31
    }
32

33
    // 检查两个位置是否连通
34
    bool is_reachable(int x1, int y1, int x2, int y2) {
35
        return _uf.connected(_encode(x1, y1), _encode(x2, y2));
36
    }
37

38
    // 获取所有不同的连通区域 → 如果 > 1, 需要额外走廊
39
    int region_count(const std::vector<std::vector<int>>& map) {
40
        std::unordered_set<int> roots;
41
        for (int i = 0; i < _rows; ++i) {
42
            for (int j = 0; j < _cols; ++j) {
43
                if (map[i][j]) {
44
                    roots.insert(_uf.find(_encode(i, j)));
45
                }
46
            }
47
        }
48
        return roots.size();
49
    }
50
};

1
// MMO 游戏中, 玩家可以组队或加入公会
2
// 两个公会合并 → Union
3
// 查询两个玩家是否同一公会 → Connected
4

5
class GuildSystem {
6
    UnionFindBySize _uf;
7
    std::unordered_map<int, std::string> _guild_names;
8

9
public:
10
    GuildSystem(int max_players) : _uf(max_players) {}
11

12
    // 创建公会 (leader 成为代表)
13
    void create_guild(int leader, const std::string& name) {
14
        _guild_names[leader] = name;
15
    }
16

17
    // 玩家加入公会 (Union 到公会 leader)
18
    void join_guild(int player, int guild_leader) {
19
        _uf.unite(player, guild_leader);
20
    }
21

22
    // 合并两个公会
23
    void merge_guilds(int leader_a, int leader_b) {
24
        _uf.unite(leader_a, leader_b);
25
    }
26

27
    // 查询两个玩家是否同一公会
28
    bool same_guild(int a, int b) {
29
        return _uf.connected(a, b);
30
    }
31

32
    // 获取公会人数
33
    int guild_size(int player) {
34
        return _uf.size_of(player);
35
    }
36
};
37

38
// 使用:
39
// GuildSystem gs(10000);
40
// gs.create_guild(1, "风暴军团");
41
// gs.join_guild(2, 1);   // 玩家2 加入 玩家1 的公会
42
// gs.join_guild(3, 1);   // 玩家3 加入
43
// gs.same_guild(2, 3);   // true
44
// gs.guild_size(1);      // 3