DSU

Given an undirected graph, it processes the following queries in $O(\alpha(n))$ time (amortized).

Edge addition
Deciding whether given two vertices are in the same connected component

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.

Constructor

dsu d(int n)

It creates an undirected graph with $n$ vertices and $0$ edges.

Constraints

$0 \leq n \leq 10^8$

Complexity

$O(n)$

merge

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

$0 \leq a < n$
$0 \leq b < n$

Complexity

$O(\alpha(n))$ amortized

same

bool d.same(int a, int b)

It returns whether the vertices $a$ and $b$ are in the same connected component.

Constraints

$0 \leq a < n$
$0 \leq b < n$

Complexity

$O(\alpha(n))$ amortized

leader

int d.leader(int a)

It returns the representative of the connected component that contains the vertex $a$.

Constraints

$0 \leq a < n$

Complexity

$O(\alpha(n))$ amortized

size

int d.size(int a)

It returns the size of the connected component that contains the vertex $a$.

Constraints

$0 \leq a < n$

Complexity

$O(\alpha(n))$ amortized

groups

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

$O(n)$

Examples

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_a

import atcoder/header import atcoder/dsu let n, q = nextInt() var d = initDSU(n) for i in 0..<q: let t, u, v = nextInt() if t == 0: d.merge(u, v) else: if d.same(u, v): echo 1 else: echo 0

Japanese API facade (experimental)

import "atcoder/extra/ja/structure/素集合データ構造"

var uf = 素集合データ構造を初期化(n)

discard uf.併合(a, b)
doAssert uf.同じ集合か(a, b)

The canonical initDSU, merge, same, leader, size, and groups APIs remain available.