This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub maspypy/library
#include "graph/blackbox/unionfind.hpp"
#include "ds/unionfind/unionfind.hpp" // 頂点を削除しながら、適当なデータ構造により次の辺を探す。 // 中身はただの bfs しているので、01 最短路にも流用可能 template <typename F1, typename F2> UnionFind blackbox_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; } vc<int> get_all() { vc<int> A(n); FOR(i, n) A[i] = (*this)[i]; return A; } }; #line 2 "graph/blackbox/unionfind.hpp" // 頂点を削除しながら、適当なデータ構造により次の辺を探す。 // 中身はただの bfs しているので、01 最短路にも流用可能 template <typename F1, typename F2> UnionFind blackbox_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; }