This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub Kyo-s-s/Library
#include "Data_structure/UnionFind.hpp"
UnionFind uf(int N);
int uf.merge(int a, int b);
int uf.leader(a)
bool uf.same(int a, int b);
int uf.size(int a);
int uf.count();
vector<vector<int>> uf.groups();
struct UnionFind { int n, cnt; vector<int> parent; UnionFind() : n(0), cnt(0) {} UnionFind(int n) : n(n), cnt(n), parent(n, -1) {} int merge(int a, int b) { assert(0 <= a && a < n && 0 <= b && b < n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent[x] < -parent[y]) swap(x, y); parent[x] += parent[y]; parent[y] = x; cnt--; return x; } int leader(int a) { assert(0 <= a && a < n); if (parent[a] < 0) return a; return parent[a] = leader(parent[a]); } bool same(int a, int b) { assert(0 <= a && a < n && 0 <= b && b < n); return leader(a) == leader(b); } int size(int a) { assert(0 <= a && a < n); return -parent[leader(a)]; } int count() { return cnt; } vector<vector<int>> groups() { vector<int> leader_buf(n), group_size(n); for (int i = 0; i < n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } vector<vector<int>> result(n); for (int i = 0; i < n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < n; i++) { result[leader_buf[i]].push_back(i); } result.erase( remove_if(result.begin(), result.end(), [&](const vector<int> &v) { return v.empty(); }), result.end()); return result; } };
#line 1 "Data_structure/UnionFind.hpp" struct UnionFind { int n, cnt; vector<int> parent; UnionFind() : n(0), cnt(0) {} UnionFind(int n) : n(n), cnt(n), parent(n, -1) {} int merge(int a, int b) { assert(0 <= a && a < n && 0 <= b && b < n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent[x] < -parent[y]) swap(x, y); parent[x] += parent[y]; parent[y] = x; cnt--; return x; } int leader(int a) { assert(0 <= a && a < n); if (parent[a] < 0) return a; return parent[a] = leader(parent[a]); } bool same(int a, int b) { assert(0 <= a && a < n && 0 <= b && b < n); return leader(a) == leader(b); } int size(int a) { assert(0 <= a && a < n); return -parent[leader(a)]; } int count() { return cnt; } vector<vector<int>> groups() { vector<int> leader_buf(n), group_size(n); for (int i = 0; i < n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } vector<vector<int>> result(n); for (int i = 0; i < n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < n; i++) { result[leader_buf[i]].push_back(i); } result.erase( remove_if(result.begin(), result.end(), [&](const vector<int> &v) { return v.empty(); }), result.end()); return result; } };