Union Find
(structure/unionFind.hpp)

• View this file on GitHub
• Last update: 2022-07-06 23:37:31+09:00
• Include: #include "structure/unionFind.hpp"

UnionFind

• 集合を効率よく扱うためのライブラリ
• 集合の合併、どの集合に属しているかを調べることができる。
• 有向グラフの場合 SCC を使うことを検討する。

実装ヒント

• ルートの data には集合サイズの-1、ルート以外の data にはその集合のルートが入る(最終的に）
• unite はもともとルートだった場所の data しか変更しないので, find でルートをたどりながら、data の更新を行う。
• groups はそれぞれの集合のベクトルを返す.

Required by

• Minimum Spanning Tree (Kruskal) (graph/maximumSpanningTree.hpp)
• graph/minimumSpanningTree.hpp

Verified with

• test/graph/kruskal.aoj_ALDS1_12_A.test.cpp
• test/union_find.aoj.test.cpp

Code

#pragma once
#include <algorithm>
#include <vector>

struct UnionFind {
  std::vector<int> data;
  UnionFind() = default;

  explicit UnionFind(size_t sz) : data(sz, -1) {}

  bool unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return false;
    if (data[a] < data[b]) std::swap(a, b);
    data[a] += data[b];
    data[b] = a;
    return true;
  }

  int find(int a) {
    if (data[a] < 0) return a;
    return data[a] = find(data[a]);
  }

  int same(int a, int b) { return find(a) == find(b); }

  int size(int k) { return -data[find(k)]; }

  std::vector<std::vector<int>> groups() {
    int n = (int)data.size();
    std::vector<std::vector<int>> ret(n);
    for (int i = 0; i < n; i++) {
      ret[find(i)].emplace_back(i);
    }
    ret.erase(std::remove_if(std::begin(ret), std::end(ret),
                        [&](const std::vector<int>& v) { return v.empty(); }),
              std::end(ret));
    return ret;
  }
};

#line 2 "structure/unionFind.hpp"
#include <algorithm>
#include <vector>

struct UnionFind {
  std::vector<int> data;
  UnionFind() = default;

  explicit UnionFind(size_t sz) : data(sz, -1) {}

  bool unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return false;
    if (data[a] < data[b]) std::swap(a, b);
    data[a] += data[b];
    data[b] = a;
    return true;
  }

  int find(int a) {
    if (data[a] < 0) return a;
    return data[a] = find(data[a]);
  }

  int same(int a, int b) { return find(a) == find(b); }

  int size(int k) { return -data[find(k)]; }

  std::vector<std::vector<int>> groups() {
    int n = (int)data.size();
    std::vector<std::vector<int>> ret(n);
    for (int i = 0; i < n; i++) {
      ret[find(i)].emplace_back(i);
    }
    ret.erase(std::remove_if(std::begin(ret), std::end(ret),
                        [&](const std::vector<int>& v) { return v.empty(); }),
              std::end(ret));
    return ret;
  }
};

Back to top page