Applications of DSU

Union-Find and Kruskal Reconstruction Tree share similar ways of thinking, as both can be used to handle problems related to connectivity. This article introduces the applications of Union-Find through example problems.

A

There are \(n\) points, initially all isolated.

Then there are \(m\) edge addition operations. The \(i\)-th operation adds an undirected edge between \(a_i\) and \(b_i\). Let \(L(i,j)\) denote the earliest operation after which nodes \(i\) and \(j\) become connected.

After all \(m\) operations, you need to compute the value of \(\sum_{i=1}^n\sum_{j=i+1}^nL(i,j)\).

This is a basic application of Union-Find, where the Union-Find records the size of each subtree. Consider counting the contribution of each operation. If in the \(i\)-th operation \(a_i\) and \(b_i\) belong to two different subtrees, merge these two subtrees and add the product of their sizes multiplied by \(i\) to the answer. Time complexity is \(O(n\alpha(n))\).

B

There are \(n\) points, initially all isolated.

Then there are \(m\) edge addition operations. The \(i\)-th operation adds an undirected edge between \(a_i\) and \(b_i\).

Then there are \(q\) queries. The \(i\)-th query asks for the earliest operation after which \(u_i\) and \(v_i\) become connected.

Consider recording the "Union-Find generation tree" during Union-Find merges. That is, if in the \(i\)-th operation \(a_i\) and \(b_i\) belong to two different subtrees, include the edge \((a_i,b_i)\) in the generation tree with edge weight \(i\). Then a query asks for the maximum edge weight on the path from \(u\) to \(v\), which can be maintained using binary lifting on trees or heavy-light decomposition. Time complexity is \(O(n\log n)\).

Another method is to maintain a Kruskal reconstruction tree, which is essentially the same as the Union-Find generation tree. The complexity is also the same.

C

There are \(n\) points, initially all isolated.

Then there are \(m\) edge addition operations. The \(i\)-th operation adds an undirected edge between \(a_i\) and \(b_i\).

Then there are \(q\) queries. The \(i\)-th query asks for the size of the connected component containing the \(x_i\)-th point after the \(t_i\)-th operation.

Offline algorithm: Sort the queries in increasing order of \(t_i\). Process the queries while adding edges using Union-Find. Time complexity is \(O(q\log q+(n+q)\alpha(n))\).

Online algorithm: The online algorithm for this problem can only use Kruskal reconstruction tree. The difference between Kruskal reconstruction tree and Union-Find is: if in the \(i\)-th operation \(a_i\) and \(b_i\) belong to two different subtrees, Kruskal creates a new node \(u\), and connects the roots of the subtrees containing \(a_i\) and \(b_i\) as the two children of \(u\). Let the weight of \(u\) be \(i\). For the initial \(n\) points, their weights are \(0\).

For a query, we only need to find the largest connected block in the reconstruction tree containing \(x_i\) such that the maximum point weight in the block does not exceed \(t_i\). The answer to the query is the number of nodes with weight \(0\) in this block, i.e., the number of leaf nodes.

Since operation indices are increasing, the parent node's weight in the reconstruction tree is always greater than its children's weights. This means we can use binary lifting on the reconstruction tree from \(x_i\) to the root to find the node with the largest weight not exceeding \(t_i\). Then we obtain the answer. Time complexity is \(O(n\log n)\).

D

Given a 01 sequence \(a_1,\ldots,a_n\) of length \(n\), initially all \(0\), perform \(m\) operations:

Set \(a_x=1\);
Find the position of the first \(0\) from left in \(a_x,a_{x+1},\ldots,a_n\).

Build a Union-Find where \(f_i\) represents the position of the first \(0\) in \(a_i,a_{i+1},\ldots,a_n\). Initially \(f_i=i\).

For an operation setting \(a_x=1\), if \(a_x\) is already \(1\), do nothing. Otherwise, set \(f_x=f_{x+1}\).

Time complexity is \(O(n\log n)\). If union by rank is used, implementation becomes more complicated but still feasible. That is, time complexity can be \(O(n\alpha(n))\).

E

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

This problem also has many solutions. Here we focus on the Union-Find approach. Consider \(c_k\) in descending order of value. This is equivalent to adding a point at \(k\), then merging the connected blocks at positions \(k-1\) and \(k+1\) with it (if there are points at those positions). Record the maximum \(a\) and maximum \(b\) in each connected block, then update the answer during merges. Time complexity is \(O(n\log n)\).

F

Given a tree with \(n\) points, perform \(m\) operations:

Add an edge from \(a_i\) to \(b_i\).
Query whether there are at least two edge-disjoint paths between \(u_i\) and \(v_i\).

A query can be transformed into: check whether \(u_i\) and \(v_i\) are on the same simple cycle. Following the idea of biconnected component contraction, each time we add an edge between \(a_i\) and \(b_i\), we can contract all points on the tree path from \(a_i\) to \(b_i\) together. If the tree paths corresponding to two edges \((a_i,b_i)\) and \((a_j,b_j)\) intersect, then these two edges will be contracted together.

In other words, an edge addition operation can be understood as covering each edge on the tree path from \(a_i\) to \(b_i\) once. The query becomes: check whether there exists any uncovered edge on the path from \(u_i\) to \(v_i\). If not, then \(u_i\) and \(v_i\) belong to the same biconnected component, i.e., the same simple cycle.

Consider using Union-Find to maintain. Root the tree, let \(f_i\) denote the first uncovered edge on the path from \(i\) to the root. For each edge addition operation, we jump through the Union-Find violently. After covering an edge, merge the \(f\) of the corresponding node with its parent. This way, each edge is covered at most once, total complexity \(O(n\log n)\). Using union by rank in Union-Find can also achieve \(O(n\alpha(n))\).

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

G

An undirected graph \(G\) has \(n\) points, initially all isolated (no edges).

Then there are \(m\) edge addition operations. The \(i\)-th operation adds an undirected edge between \(a_i\) and \(b_i\).

After each operation, you need to output the number of bridges in the graph.

A bridge is defined as: for an edge \((x,y)\) in \(G\), if removing it increases the number of connected components, then \((x,y)\) is called a bridge.

Forced online.

This problem tests the understanding of Union-Find properties. Consider using Union-Find to maintain connectivity. For the edge-biconnected tree, consider maintaining a rooted tree, let \(p_i\) denote the parent of node \(i\). This is essentially Union-Find without path compression.

If in the \(i\)-th operation \(a_i\) and \(b_i\) belong to the same connected component, then we need to contract all points on the path from \(a_i\) to \(b_i\) in the edge-biconnected tree. This can be maintained with Union-Find. Each contraction reduces the number of edge-biconnected components by \(1\), at most \(n-1\) times, so the Union-Find complexity for contraction is \(O(n\alpha(n))\).

To contract, we first need to find the LCA of \(a_i\) and \(b_i\) in the edge-biconnected tree. For this we can maintain a marking array. Then start from \(a_i\) and \(b_i\) alternately moving up along ancestors one by one, marking visited points. Once we jump to a point that was marked before, that point is the LCA of \(a_i\) and \(b_i\). The complexity of this algorithm is linear in the path length from \(a_i\) to \(b_i\), which is acceptable.

If \(a_i\) and \(b_i\) belong to two different connected components, then we merge these two components and increase the bridge count by \(1\). Now we need to connect the two edge-biconnected trees, i.e., add an edge between \(a_i\) and \(b_i\). Therefore we need to reroot one tree and attach it to the other. Here we apply the idea of heuristic merge: reroot the tree with fewer nodes. The total complexity is \(O(n\log n)\).

In summary, the total complexity of this algorithm is \(O(n\log n+m\log n)\).

Summary

Union-Find and Kruskal reconstruction tree have many common points, and the optimization of Union-Find (union by rank) is an application of heuristic merge. Therefore, flexible use of Union-Find can conveniently handle many graph theory problems related to connectivity.

Parts of this page are translated from the blog post Поиск мостов в режиме онлайн and its English translation 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.

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用