acl_cpp.dsu

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 \lt 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 \lt n\)
\(0 \le b \lt 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 \lt n\)
\(0 \le b \lt 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 \lt 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 \lt 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)))