This is not to be confused with DSU on Tree (Sack).
What can a Reachability Tree do?
Suppose you are given a weighted (connected) undirected graph of $$$N$$$ vertices and $$$M$$$ edges. Let's define an ordering of the edges, for example, the edges are ordered in the ascending/descending order of their weights. The reachability tree can help you with:
- Find the minimal/maximal weight of the edges when traversing from vertex $$$u$$$ to vertex $$$v$$$.
- Find the set of vertices that are reachable from a given vertex using the first $$$x$$$ edges, for some arbitrary $$$x$$$. You can store some information in this set of reachable vertices, such as the maximum value or the sum of values of all the reachable vertices.
Constructing a Reachability Tree
The reachability tree is a rooted tree that consists of $$$N + M$$$ nodes. The tree will have $$$N$$$ leaves which represent the original vertices of the graph, and the rest of $$$M$$$ internal nodes represent the edges of the original graph.
To build this tree, we start with the $$$N$$$ leaves, then iterate the edges of the graph one by one starting from the smallest one to the largest one. When adding an edge that connects $$$u$$$ and $$$v$$$, add a new node to the tree, then attach the current root(s) of $$$u$$$ and $$$v$$$ in the trees as the children of the newly added node. Finding these roots can be done using DSU data structure.
You can think of the reachability tree as a DSU but with no path compression, so each subtree of some internal node in the reachability tree is the set of vertices in the connected component that contains the associated edge at the point when you were adding it.
When possible, you may omit the edges that connect two vertices from the same connected component, and the reachability tree you end up with will only have $$$2N - 1$$$ nodes.
Example code
Following is a simplified version of reachability tree codeint getRoot(int u) {
if (u == dsu[u]) return u;
return dsu[u] = getRoot(dsu[u]);
}
void addEdge(int u, int v) {
u = getRoot(u); v = getRoot(v);
dsu[n] = n;
dsu[u] = dsu[v] = n;
adj[n].push_back(u);
if (u != v) adj[n].push_back(v);
++n;
}
void build() {
for (int i = 0; i < n; ++i) dsu[i] = i;
for (int i = 0; i < m; ++i) addEdge(U[i], V[i]);
}
Solving example problems
Given an undirected graph with $$$N$$$ vertices and $$$M$$$ edges. Each vertex has a value written on it. You have to process two types of queries:
- Given a vertex $$$v$$$, among all vertices currently reachable from $$$v$$$, find the vertex with the largest value, output it, then replace its value with $$$0$$$.
- Delete a given edge $$$e$$$.
SolutionWe will build a reachability tree while processing the queries backward so that deletion of an edge can be seen as addition of an edge. Whenever we process a query of the second type, add this edge to the reachability tree (by creating a new node and attach to the roots of the two connecting vertices). When processing a query of the first type, we store the current root of this vertex, which we will answer later on.
After the reachability tree is built, we process the queries again (this time in forward order). We can now answer the queries of the first type as a subtree-maximum query, while you can skip the query of the second type. Do an Eulerian tour on our reachability tree so that each subtree can be represented as a segment, then we can use a segment tree to process all our queries.
Given an undirected weighted graph of $$$N$$$ vertices and $$$M$$$ edges. Given $$$Q$$$ queries, in each query, suppose there are two people at vertices $$$X$$$ and $$$Y$$$. These two people want to switch places ($$$X$$$ moves to $$$Y$$$, and $$$Y$$$ moves to $$$X$$$), but they must not meet each other at any point of time when traversing the graph. The cost of a switch is the maximum weight traversed by both people. Compute the minimum cost, or tell that they can't switch places without meeting each other. Queries have to be processed online.
SolutionIf the queries can be processed offline, then this problem can be solved using parallel binary search.
Let's solve the online version. First, observe that two people can switch places if and only if they are in the same connected component, and either the component they are in contains a vertex with degree at least $$$3$$$ or the component contains a cycle. We say a connected component to be switchable if any two people from two different vertices from this connected component can switch places.
We will build a reachability tree by adding the edges from the smallest weight to the largest weight. After adding an edge, check whether the connected component where the newly added edge is in is switchable. If it is switchable, mark this newly added node in the reachability tree as switchable.
When given a query with vertices $$$X$$$ and $$$Y$$$, find the LCA of these two nodes in the reachability tree. From the LCA, find the nearest ancestor (possibly the LCA itself) that is switchable, then the weight of the edge corresponding to this node will be the answer to this query. All of these can be done with the help of sparse tables.
Given an undirected graph with $$$N$$$ vertices and $$$M$$$ edges. Vertices are numbered from $$$0$$$ through $$$N - 1$$$. You are given $$$Q$$$ queries, each represented as four integers $$$S$$$, $$$E$$$, $$$L$$$, $$$R$$$ ($$$L \le S$$$ and $$$E \le R$$$). You want to know whether it is possible to travel from $$$S$$$ to $$$E$$$ satisfying: suppose you visit the vertices $$$V_0, V_1, \dots, V_p$$$ in this order, there exists $$$q$$$ such that $$$L \le V_0, V_1, \dots, V_q$$$ and $$$V_q, V_{q + 1}, \dots, V_p \le R$$$.
SolutionWe will build two reachability trees. We will focus on the method of building one of the trees, the other one can be done similarly.
Unlike the usual reachability tree where we add edges, we will add the vertices in descending order of indices. The reachability tree starts with $$$N$$$ nodes representing the original vertices, then whenever we add a vertex, add a new node to the tree, then consider all the neighbours that have been added so far. For each of these neighbours, find its root in the current reachability tree. All these roots will then be attached as the children of the newly added node. From the resulting tree so far, for all queries with $$$L$$$ equal to the currently added vertex number, find the root of $$$S$$$. This means the set of reachable vertices from $$$S$$$ and $$$\le L$$$ can be represented as a subtree of this root node.
Perform DFS, then we can order the leaves of the reachability tree according to their preorder numbering. Hence, each subtree can now be represented as a segment $$$[x_l, x_r]$$$.
The other reachability tree for reachable vertices from $$$E$$$ and $$$\ge R$$$ can be built similarly by adding vertices in ascending order of indices.
To answer the query, we can check whether the two segments have a number that intersects. Unfortunately, we cannot simply intersect ranges as a vertex can have different preorder numbering in both trees. Let the preorder numbering of a vertex from both trees be $$$x$$$ and $$$y$$$, then we can represent this vertex as a point $$$(x, y)$$$ on a two-dimensional plane. In this scenario, our query can now be answered by querying whether there exists a point in the rectangle $$$[x_l, x_r] \times [y_l, y_r]$$$, where $$$[x_l, x_r]$$$ and $$$[y_l, y_r]$$$ are the ranges represented by the corresponding subtrees of this query. This checking can be done using segment tree.
More example problems
Thank you to the people who provided me with these example problems, here are what I have so far:
If you have more example problems or any suggestions, please let us know.