acl_cpp.dsu

• C++ version documentation

• Source code

dsu.dsu

# dsu
from acl_cpp.dsu import dsu

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

• adding edges

• Deciding whether given two vertices are in the same connected component

Here, $\alpha (n)$ is the inverse Ackermann function, which can be considered almost constant time.

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::dsu(int n)
def dsu(n: int = 0) -> dsu

• Creates an undirected graph with $n$ vertices and $0$ edges.

Constraints

• $0\le n<2^{31}$

Complexity

• $O(n)$

dsu.merge

# void dsu::merge(int a, int b)
def dsu.merge(a: int, b: int) -> None

Adds an edge $(a,b)$.

Returns the representative if $a$ and $b$ were already connected, otherwise returns the new representative.

Constraints

• $0\le a<n$

• $0\le b<n$

Complexity

• Amortized $O(\alpha (n))$

dsu.same

# bool dsu::same(int a, int b)
def dsu.same(a: int, b: int) -> bool

Returns whether vertices $a$ and $b$ are connected.

Constraints

• $0\le a<n$

• $0\le b<n$

Complexity

• Amortized $O(\alpha (n))$

dsu.leader

# int dsu::leader(int a)
def dsu.leader(a: int) -> int

Returns the representative of the connected component containing vertex $a$.

Constraints

• $0\le a<n$

Complexity

• Amortized $O(\alpha (n))$

dsu.size

# int dsu::size(int a)
def dsu.size(a: int) -> int

Returns the size of the connected component containing vertex $a$.

Constraints

• $0\le a<n$

Complexity

• Amortized $O(\alpha (n))$

dsu.groups

# vector<vector<int>> dsu::groups()
def dsu.groups() -> list[list[int]]

Divides the graph into connected components and returns that information.

The return value is a list of lists of vertex numbers, each representing a connected component. The order of vertices within each list and the order of the lists themselves are undefined.

Complexity

• $O(n)$

Examples

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

from acl_cpp.dsu import dsu

N, Q = map(int, input().split())
d = dsu(N)

for _ in range(Q):
    t, u, v = map(int, input().split())
    if t == 0:
        d.merge(u, v)
    else:
        print(int(d.same(u, v)))