[Tutorial] Reachability Tree / DSU-tree

Revision en4, by prabowo, 2020-12-19 08:27:08

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 code

Solving example problems

CF1416D – Graph and Queries

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:

  1. 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$$$.
  2. Delete a given edge $$$e$$$.
Solution

APIO 2020 – Swapping Cities

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.

Solution

IOI 2018 – Werewolf

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$$$.

Solution

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.

Tags data structure, reachability tree, dsu, tutorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English prabowo 2020-12-19 08:27:08 38 Fix buggy pseudo code
en3 English prabowo 2020-12-19 07:33:22 116 Add more example problem
en2 English prabowo 2020-12-19 06:08:12 47 (published)
en1 English prabowo 2020-12-18 21:21:59 8451 Initial revision (saved to drafts)