Applications of Disjoint-Set Union

The ideas behind disjoint-set union and the Kruskal reconstruction tree are very similar, and both can be used to process connectivity-related problems. This article introduces applications of the disjoint-set union technique through examples.

A

A

There are $n$ vertices, all isolated initially.

Next, there are $m$ edge-addition operations. Operation $i$ adds an undirected edge between $a_i$ and $b_i$. Let $L(i,j)$ denote the earliest operation after which vertices $i$ and $j$ become connected, that is, after operation $L(i,j)$.

After all $m$ operations, find the value of $\sum_{i=1}^n\sum_{j=i+1}^nL(i,j)$.

This is a basic application of disjoint-set union: maintain the size of each component and consider the contribution of every operation. If $a_i$ and $b_i$ belong to two different components during operation $i$, merge the two components and add the product of their sizes multiplied by $i$ to the answer. The time complexity is $O(n\alpha(n))$.

B

B

There are $n$ vertices, all isolated initially.

Next, there are $m$ edge-addition operations. Operation $i$ adds an undirected edge between $a_i$ and $b_i$.

Next, there are $q$ queries. In query $i$, determine after which operation vertices $u_i$ and $v_i$ first become connected.

When merging components in disjoint-set union, maintain a “disjoint-set union spanning tree”: if $a_i$ and $b_i$ belong to different components during operation $i$, include the edge $(a_i,b_i)$ in the spanning tree, with edge weight $i$. A query then asks for the maximum edge weight on the path from $u$ to $v$, which can be maintained using binary lifting or heavy-light decomposition. The time complexity is $O(n\log n)$.

Another method is to maintain a Kruskal reconstruction tree. Its essence is the same as that of the disjoint-set union spanning tree, and its complexity is also the same.

C

C

There are $n$ vertices, all isolated initially.

Next, there are $m$ edge-addition operations. Operation $i$ adds an undirected edge between $a_i$ and $b_i$.

Next, there are $q$ queries. In query $i$, determine the size of the connected component containing vertex $x_i$ after operation $t_i$.

Offline algorithm: sort the queries in increasing order of $t_i$. Process the queries while adding edges with a disjoint-set union. The time complexity is $O(q\log q+(n+q)\alpha(n))$.

Online algorithm: the online algorithm for this problem can use only a Kruskal reconstruction tree. The difference from disjoint-set union is that, when $a_i$ and $b_i$ belong to different components during operation $i$, Kruskal creates a new vertex $u$, then connects the roots of the components containing $a_i$ and $b_i$ to $u$ as $u$'s two children. Let the vertex weight of $u$ be $i$. The initial $n$ vertices have vertex weight $0$.

For a query, we only need to find the largest connected component containing $x_i$ in the reconstruction tree such that the maximum vertex weight in the component does not exceed $t_i$. The answer is the number of vertices in this component whose vertex weight is $0$, that is, the number of leaf vertices.

Since the operation indices are increasing, the vertex weight of a parent in the reconstruction tree is always greater than that of its child. Therefore, on the path from $x_i$ to the root, we can use binary lifting to find the vertex with the largest weight not exceeding $t_i$. This gives the answer. The time complexity is $O(n\log n)$.

D

D

Given a binary sequence $a_1,\ldots,a_n$ of length $n$, initially all $0$, perform $m$ operations:

• Set $a_x=1$.
• Find the leftmost position whose value is $0$ among $a_x,a_{x+1},\ldots,a_n$.

Maintain a disjoint-set union where $f_i$ is the position of the first $0$ among $a_i,a_{i+1},\ldots,a_n$. Initially, $f_i=i$.

For an operation setting $a_x=1$, do nothing if $a_x$ was already $1$; otherwise, set $f_x=f_{x+1}$.

The time complexity is $O(n\log n)$. Using union by rank is somewhat cumbersome to implement, but it is still possible; in that case, the time complexity can be $O(n\alpha(n))$.

E

E

Given three sequences $a$, $b$, and $c$ of positive integers of length $n$, enumerate $1\le i\le j\le n$ and find the maximum value of $a_i\cdot b_j\cdot \min_{i\le k\le j}c_k$.

There are also many ways to solve this problem; here we focus on the disjoint-set union approach. Consider $c_k$ in decreasing order of value. Equivalently, add a vertex at position $k$, then merge it with the components containing positions $k-1$ and $k+1$ if those positions already contain vertices. Store the maximum value of $a$ and the maximum value of $b$ in each component, and update the answer during merges. The time complexity is $O(n\log n)$.

F

F

Given a tree with $n$ vertices, perform $m$ operations:

• Add an edge from $a_i$ to $b_i$.
• Ask whether there are at least two edge-disjoint paths between $u_i$ and $v_i$.

The query can be transformed into asking whether $u_i$ and $v_i$ lie on the same simple cycle. Following the idea of contracting biconnected components, whenever an edge is added between $a_i$ and $b_i$, contract all vertices on the tree path from $a_i$ to $b_i$. If the tree paths corresponding to two added edges $(a_i,b_i)$ and $(a_j,b_j)$ intersect, those edges are contracted together.

In other words, an edge-addition operation can be viewed as covering every edge on the tree path from $a_i$ to $b_i$ once. The query becomes checking whether there is an uncovered edge on the path from $u_i$ to $v_i$. If there is none, then $u_i$ and $v_i$ belong to the same biconnected component, and hence to the same simple cycle.

Use disjoint-set union to maintain this structure. Root the tree, and let $f_i$ be the first uncovered edge on the path from $i$ to the root. For each edge-addition operation, repeatedly jump using disjoint-set union. After covering an edge, merge the $f$ of the corresponding vertex with its parent. Each edge is covered at most once, so the total complexity is $O(n\log n)$. Union by rank can likewise achieve $O(n\alpha(n))$.

The maintenance method is similar to the tree version of D.

G

G

An undirected graph $G$ has $n$ vertices, all isolated initially (that is, it has no edges).

Next, there are $m$ edge-addition operations. Operation $i$ adds an undirected edge between $a_i$ and $b_i$.

After every operation, find the number of bridges in the graph.

An edge $(x,y)$ in $G$ is called a bridge if deleting it increases the number of connected components; then $(x,y)$ is a bridge.

The algorithm must be online.

This problem tests one’s understanding of disjoint-set union. Use disjoint-set union to maintain connectivity. For the bridge tree, maintain a rooted tree and let $p_i$ denote the parent of vertex $i$; this is disjoint-set union without path compression.

If, during operation $i$, $a_i$ and $b_i$ belong to the same connected component, contract the vertices on the path between $a_i$ and $b_i$ in the bridge tree, which can be maintained with disjoint-set union. Each contraction decreases the number of biconnected components by $1$, and there can be at most $n-1$ contractions, so the disjoint-set union complexity of the contraction part is $O(n\alpha(n))$.

To contract the path, first find the LCA of $a_i$ and $b_i$ in the bridge tree. Maintain a marker array. Starting from $a_i$ and $b_i$, alternately jump upward one ancestor at a time and mark every visited vertex. Once a vertex that was marked previously is reached, it is the LCA of $a_i$ and $b_i$. The complexity is linear in the length of the path from $a_i$ to $b_i$, which is acceptable.

If $a_i$ and $b_i$ belong to different connected components, merge the two components and increase the number of bridges by $1$. We must connect the two bridge trees by adding an edge from $a_i$ to $b_i$. Thus, one of the trees must be rerooted and attached to the other. Using the idea of heuristic merging, reroot the tree with fewer vertices. The total complexity is $O(n\log n)$.

Therefore, the total complexity of the algorithm is $O(n\log n+m\log n)$.

Summary

Disjoint-set union and Kruskal reconstruction trees have many points in common, and the disjoint-set union optimization of union by rank is itself an application of heuristic merging. Therefore, flexible use of disjoint-set union can conveniently handle many graph-theoretic problems related to connectivity.

Part of this page is adapted from the blog post Finding Bridges Online and its English-language edition Finding Bridges Online. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.