概要

辺で繋がれた頂点たちが同じグループに属するか、という問題を木構造で管理します。

AtCoderのの解説スライドがとてもわかりやすいです。

Union Find – AtCoder Typical Contest 001

サンプルコード

struct UnionFind {
  vector<int> parent;
  vector<int> num_node;

  UnionFind(int N) : parent(N), num_node(N, 1) {
    for (int i = 0; i < N; i++) {
      parent[i] = i;
    }
  }

  // 根を求める
  int root(int x) {
    if (parent[x] == x) {
      return x;
    }

    // 経路圧縮
    parent[x] = root(parent[x]);
    return parent[x];
  }

  // 同一判定
  bool is_same(int x, int y) {
    return this->root(x) == this->root(y);
  }

  // 併合
  void unite(int x, int y) {
    x = this->root(x);
    y = this->root(y);

    // すでに一緒ならなにもしない
    if (x == y) {
      return;
    }
    parent[x] = y;
    num_node[y] += num_node[x];
  }

  // 同一グループのノード数
  int size(int x) {
    return num_node[root(x)];
  }
};

UnionFind木

概要

サンプルコード

関連問題