graph/implicit_graph/unionfind.hpp

• View this file on GitHub
• Last update: 2023-06-11 17:06:39+09:00
• Include: #include "graph/implicit_graph/unionfind.hpp"

Depends on

• ds/unionfind/unionfind.hpp

Verified with

• test/yukicoder/1170_2.test.cpp

Code

#include "ds/unionfind/unionfind.hpp"

// 頂点を削除しながら、適当なデータ構造により次の辺を探す。
// 中身はただの bfs しているので、01 最短路にも流用可能
template <typename F1, typename F2>
UnionFind implicit_graph_unionfind(int N, F1 set_used, F2 find_unused) {
  UnionFind uf(N);
  vc<bool> done(N);
  deque<int> que;
  FOR(v, N) if (!done[v]) {
    que.eb(v);
    done[v] = 1;
    set_used(v);
    while (!que.empty()) {
      int x = que.front();
      que.pop_front();
      set_used(x);
      done[x] = 1;
      while (1) {
        int to = find_unused(x);
        if (to == -1) break;
        uf.merge(v, to);
        que.eb(to);
        done[to] = 1;
        set_used(to);
      }
    }
  }
  return uf;
}

#line 2 "ds/unionfind/unionfind.hpp"

struct UnionFind {
  int n, n_comp;
  vc<int> dat; // par or (-size)
  UnionFind(int n = 0) { build(n); }

  void build(int m) {
    n = m, n_comp = m;
    dat.assign(n, -1);
  }

  void reset() { build(n); }

  int operator[](int x) {
    while (dat[x] >= 0) {
      int pp = dat[dat[x]];
      if (pp < 0) { return dat[x]; }
      x = dat[x] = pp;
    }
    return x;
  }

  ll size(int x) {
    x = (*this)[x];
    return -dat[x];
  }

  bool merge(int x, int y) {
    x = (*this)[x], y = (*this)[y];
    if (x == y) return false;
    if (-dat[x] < -dat[y]) swap(x, y);
    dat[x] += dat[y], dat[y] = x, n_comp--;
    return true;
  }
};
#line 2 "graph/implicit_graph/unionfind.hpp"

// 頂点を削除しながら、適当なデータ構造により次の辺を探す。
// 中身はただの bfs しているので、01 最短路にも流用可能
template <typename F1, typename F2>
UnionFind implicit_graph_unionfind(int N, F1 set_used, F2 find_unused) {
  UnionFind uf(N);
  vc<bool> done(N);
  deque<int> que;
  FOR(v, N) if (!done[v]) {
    que.eb(v);
    done[v] = 1;
    set_used(v);
    while (!que.empty()) {
      int x = que.front();
      que.pop_front();
      set_used(x);
      done[x] = 1;
      while (1) {
        int to = find_unused(x);
        if (to == -1) break;
        uf.merge(v, to);
        que.eb(to);
        done[to] = 1;
        set_used(to);
      }
    }
  }
  return uf;
}

Back to top page