Given an undirected graph, it processes the following queries in $O(\alpha(n))$ time (amortized).
Each connected component internally has a representative vertex.
When two connected components are merged by edge addition, one of the two representatives of these connected components becomes the representative of the new connected component.
dsu d(int n)
Constraints
Complexity
int d.merge(int a, int b)
It adds an edge $(a, b)$.
If the vertices $a$ and $b$ were in the same connected component, it returns the representative of this connected component. Otherwise, it returns the representative of the new connected component.
Constraints
Complexity
bool d.same(int a, int b)
It returns whether the vertices $a$ and $b$ are in the same connected component.
Constraints
Complexity
int d.leader(int a)
It returns the representative of the connected component that contains the vertex $a$.
Constraints
Complexity
int d.size(int a)
It returns the size of the connected component that contains the vertex $a$.
Constraints
Complexity
vector<vector<int>> d.groups()
It divides the graph into connected components and returns the list of them.
More precisely, it returns the list of the "list of the vertices in a connected component". Both of the orders of the connected components and the vertices are undefined.
Complexity