并查集简介

英文名: Union & Find

并查集是一种树形结构，用于处理集合的合并和查询。

实现:

• 每个集合用一棵树表示
• 每个节点存储它的父节点
• 树根的编号代表集合的编号

优化:

• 按秩合并
• 路径压缩: 推荐
• 路径压缩 和 按秩合并: 矛盾
• 路径压缩 和 按量合并: 自己提出

5个O(1):

• findRoot(x): 平均O(1) 找到集合编号
• isConnected(x,y): 平均O(1) 判断2个节点是否属于同一个集合
• toUnion(x,y): 平均O(1) 合并2个节点所属的集合
• count(x): 平均O(1) 获取节点所属集合的节点的数量
• size(): O(1) 获取总的集合的数量

路径压缩 的时间复杂度

1、多次 findRoot 的时间复杂度平均 O(1)

findRoot前:      findRoot(7):        再次findRoot(7):
                 时复 O(log(n))      时复 O(1)
    1                 1                   1
   / \            / / | \             / / | \
  2   3          2 3  4  7           2 3  4  7
 / \  |          | |                 | |
4   5 6          5 6                 5 6
|
7

2、findRoot 的时间复杂度最差 O(log(n))，小常数的 O(log(n)) 可以看作 O(1)

路径压缩 和 按秩合并 同时使用的2个问题

1、活跃的集合 和 不活跃的集合合并，不活跃的集合的 rank 大的概率更高

操作 toUnion(1, 7)
合并前:             按秩合并后:         按量合并后:
     1       7              7                 1
 / / | \ \   |            /   \          / / / \ \ \
2 3  4  5 6  8           1     8        2 3 4   5 6 7
             |       / / | \ \  \                   |
             9      2 3  4  5 6  9                  8
                                                    |
                                                    9

虽然 按量合并 的高度大于 按秩合并，但是之后的 路径压缩 需要调整节点少。

2、使用 路径压缩 时，无法正确维持 rank

findRoot前:         findRoot(4)后:
rank: 3             rank: 3 (错误)
  1                      1
 / \                 / / | \
2   5               2 3  4  5
|   |                       |
3   6                       6
|
4

findRoot 无法正确维持 rank，即使用 路径压缩 时，无法正确使用 按秩合并。

并查集的通用模板

class UnionFind {
  struct Node {
    explicit Node(int root = 0) : root(root), cnt(1) {}
    int root;
    int cnt;
  };

 public:
  explicit UnionFind(int capacity) : nodeVec(capacity), size0(capacity) {
    for (int x = 0; x < capacity; ++x) {
      nodeVec[x].root = x;
    }
  }
  inline bool isConnected(int x, int y) { return findRoot(x) == findRoot(y); }
  bool toUnion(int x, int y) {
    int xRoot = findRoot(x);
    int yRoot = findRoot(y);
    if (xRoot != yRoot) {
      if (nodeVec[xRoot].cnt < nodeVec[yRoot].cnt) {
        nodeVec[xRoot].root = yRoot;
        nodeVec[yRoot].cnt += nodeVec[xRoot].cnt;
      } else {
        nodeVec[yRoot].root = xRoot;
        nodeVec[xRoot].cnt += nodeVec[yRoot].cnt;
      }
      --size0;
      return true;
    }
    return false;
  }
  inline int count(int x) { return nodeVec[findRoot(x)].cnt; }
  inline int size() const { return size0; }

 private:
  int findRoot(int x) {
    int root = x;
    while (nodeVec[root].root != root) {
      root = nodeVec[root].root;
    }
    while (nodeVec[x].root != root) {
      const int y = nodeVec[x].root;
      nodeVec[x].root = root;
      x = y;
    }
    return root;
  }
  vector<Node> nodeVec;
  int size0;
};

并查集的基础题目

AcWing 836. 合并集合

使用并查集的通用模板

#include <iostream>
#include <vector>
using namespace std;

int main(void) {
  int n, m, a, b;
  char oper[4];
  scanf("%d%d", &n, &m);
  UnionFind unionFind(n);
  for (int i = 0; i < m; ++i) {
    scanf("%1s%d%d", oper, &a, &b);
    if (oper[0] == 'M') {
      unionFind.toUnion(a - 1, b - 1);
    } else if (oper[0] == 'Q') {
      puts(unionFind.isConnected(a - 1, b - 1) ? "Yes" : "No");
    }
  }
  return 0;
}

AcWing 837. 连通块中点的数量

使用并查集的通用模板

#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

int main(void) {
  int n, m, a, b;
  char oper[4];
  scanf("%d%d", &n, &m);
  UnionFind unionFind(n);
  for (int i = 0; i < m; ++i) {
    scanf("%2s", oper);
    if (!strcmp("C", oper)) {
      scanf("%d%d", &a, &b);
      unionFind.toUnion(a - 1, b - 1);
    } else if (!strcmp("Q1", oper)) {
      scanf("%d%d", &a, &b);
      puts(unionFind.isConnected(a - 1, b - 1) ? "Yes" : "No");
    } else if (!strcmp("Q2", oper)) {
      scanf("%d", &a);
      printf("%d\n", unionFind.count(a - 1));
    }
  }
  return 0;
}

LeetCode 200. Number of Islands

使用并查集的通用模板

class Solution {
 public:
  static int numIslands(const vector<vector<char>>& grid) {
    if (grid.empty() || grid[0].empty()) {
      return 0;
    }
    const int m = static_cast<int>(grid.size());
    const int n = static_cast<int>(grid[0].size());
    UnionFind unionFind(m * n);
    int landSize = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == '1') {
          if (i > 0 && grid[i - 1][j] == '1') {
            unionFind.toUnion((i - 1) * n + j, i * n + j);
          }
          if (j > 0 && grid[i][j - 1] == '1') {
            unionFind.toUnion(i * n + j, i * n + j - 1);
          }
          ++landSize;
        }
      }
    }
    landSize -= m * n - unionFind.size();
    return landSize;
  }
};

LeetCode 547. Friend Circles

使用并查集的通用模板

class Solution {
 public:
  static int findCircleNum(const vector<vector<int>>& mat) {
    if (mat.empty() || mat.size() != mat[0].size()) {
      return 0;
    }
    const int n = static_cast<int>(mat.size());
    UnionFind unionFind(n);
    for (int i = 1; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (mat[i][j]) {
          unionFind.toUnion(i, j);
        }
      }
    }
    return unionFind.size();
  }
};

LeetCode 684. Redundant Connection

使用并查集的通用模板

class Solution {
 public:
  static vector<int> findRedundantConnection(const vector<vector<int>>& edges) {
    if (edges.empty()) {
      return {-1, -1};
    }
    const int n = static_cast<int>(edges.size());
    UnionFind unionFind(n + 1);
    for (int i = 0; i < n; ++i) {
      const int u = edges[i][0];
      const int v = edges[i][1];
      if (!unionFind.toUnion(u, v)) {
        return {u, v};
      }
    }
    return {-1, -1};
  }
};

AcWing 859. Kruskal算法求最小生成树

使用并查集的通用模板

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;

class Graph {
  struct Edge {
    int v0;
    int v1;
    int weight;
  };

 public:
  explicit Graph(int vertexSize, int edgeCapacity = 256) : vertexSize0(vertexSize) {
    edgeVec.reserve(edgeCapacity);
  }
  void push(int v0, int v1, int weight) { edgeVec.push_back({v0, v1, weight}); }
  int sumMinTreeDist() {
    sort(edgeVec.begin(), edgeVec.end(),
         [](const Edge &edge0, const Edge &edge1) { return edge0.weight < edge1.weight; });
    UnionFind unionFind(vertexSize0);
    const int edgeSize0 = static_cast<int>(edgeVec.size());
    int res = 0;
    for (int i = 0; i < edgeSize0; ++i) {
      if (unionFind.toUnion(edgeVec[i].v0, edgeVec[i].v1)) {
        res += edgeVec[i].weight;
      }
    }
    if (unionFind.size() != 1) {
      return DIST_MAX;
    }
    return res;
  }
  static constexpr int DIST_MAX = INT_MAX / 2;

 private:
  int vertexSize0;
  vector<Edge> edgeVec;
};
constexpr int Graph::DIST_MAX;

int main(void) {
  int n, m, u, v, w;
  scanf("%d%d", &n, &m);
  Graph graph(n, m);
  for (int i = 0; i < m; ++i) {
    scanf("%d%d%d", &u, &v, &w);
    graph.push(u - 1, v - 1, w);
  }
  const int sumDist = graph.sumMinTreeDist();
  if (sumDist == Graph::DIST_MAX) {
    puts("impossible");
  } else {
    printf("%d", sumDist);
  }
  return 0;
}