Rare
 0/4

Critical

Authors: Benjamin Qi, Mihnea Brebenel, Kevin Sheng

Finding nodes that must be visited along any path.

Edit This Page

Prerequisites

  • Gold - Cycle Finding

Focus Problem – try your best to solve this problem before continuing!

Resources
Princeton

Made by the creator of the algorithm himself!

Wiki

Wiki Definition

Blog
Blog

Initial Approach

These critical nodes that the problem talks about are commonly known as dominators. Let's define dom(u)\texttt{dom}(u) as the set of nodes that dominate node uu.

The dominator of the starting node is itself, and the set of dominators for any other node uu is the intersection of the set of dominators for all ancestors pp of node uu.

dom(u)={u if u is the starting pointu(pancestor(u)dom(p))otherwise\texttt{dom}(u)= \begin{cases} u\quad\text{ if } u \text{ is the starting point} \\ {u}\cup \left(\bigcap_{p \in \texttt{ancestor}(u)} \texttt{dom}(p)\right)\quad\text{otherwise} \end{cases}

Implementation

The following code uses the above recurrence. However, it's too slow and uses too much memory. We'll try to optimize this moving on!

Time complexity: O(N2)\mathcal{O}(N^2).

C++

#include <bitset>
#include <iostream>
#include <vector>
using std::bitset;
using std::cout;
using std::endl;
using std::vector;
const int MAX_N = 1e5;

Optimizing With Trees

In this approach, we are going to build the dominator tree of the graph.

Before we discuss this though, let's set up some terms we're going to use throughout this module:

  • A node uu strictly dominates another node vv if uu dominates vv and uvu \ne v.
  • Let the immediate dominator of uu, or idom(u)\texttt{idom}(u), be the unique node vv such that it strictly dominates node uu and every other dominator of node uu strictly dominates node vv.
  • Let e(u)e(u) be the entry time in node uu doing a Euler tour.
  • Let the semi-dominator of uu, or sdom(u)\texttt{sdom}(u), be a vv such that there's a path from vv to uu and e(i)e(u)e(i) \ge e(u) for every intermediate node ii along the path from uu to vv, excluding the ends. If there's multiple nodes that satisfy this requirement, we take the node vv with the smallest e(v)e(v).
  • Let the relative dominator of uu, or rdom(u)\texttt{rdom}(u), be the vertex xsdom(u)x \ne \texttt{sdom}(u) on the path from sdom(u)\texttt{sdom}(u) to uu in the Euler tour tree with the lowest sdom node number. Unlike with the sdom, ties in this function can be broken arbitrarily.

A dominator tree is a tree where each node's children are those nodes it immediately dominates. The start node is the root of the tree.

Given this definition, we can see that if a node dominates another, then the former is an ancestor of the latter in the dominator tree. Thus, the answer to the CSES problem is the set of all nodes that lie on the path from the root to node nn in the tree.

The following graph shows the sdom for every node. The full-color edges represent the edges part of the DFS tree.

Graph2

Important properties

Proofs of these properties are located later in the module. For all of these properties, let uu be a node that isn't the starting node.

  1. sdom(u)\texttt{sdom}(u) is a proper ancestor of uu is the DFS tree.
  2. If rdom(u)=u\texttt{rdom}(u)=u, then idom(u)=sdom(u)\texttt{idom}(u)=\texttt{sdom}(u).
  3. If not, then idom(u)=idom(rdom(u))\texttt{idom}(u)=\texttt{idom}(\texttt{rdom}(u))

Algorithm Overview

Before we get into the nitty-gritty, here's a brief outline of how exactly we're going to build up this dominator tree.

  1. Compute the sdom of every node besides the start.
  2. Compute the rdom of every node besides the start.
  3. Visit all the vertices in the DFS tree and calculate their immediate dominator using the second and third properties that were listed above. Notice that due to how we defined the rdom of a node, a preorder traversal will always visit the rdom of a node before the node itself if the two aren't the same.

The first and second steps are awfully vague- let's clear those up now, shall we?

Computing sdom\texttt{sdom}

We can compute sdom(u)\texttt{sdom}(u) as the minimum node in the intersection of the following groups:

  1. All the nodes yy such that there's an edge from yy to uu and e(y)e(u)e(y) \le e(u).
  2. All the values of sdom(x)\texttt{sdom}(x) where xx is any node such that there's an edge from uu to xx and e(x)>e(u)e(x) > e(u). To be more mathematically precise, we can define this group as
    {sdom(x)  (u,x)E and e(x)>e(u)}\{\texttt{sdom}(x)\ |\ (u, x) \in E\text{ and }e(x)>e(u)\}

The proof of why this works is beyond the scope of this module.

Implementing sdom\texttt{sdom}

We first perform a preorder DFS traversal of the graph from the source node and keep track of all the entry times of the nodes.

Then, we compute the sdom for all nodes by applying the formula mentioned in the previous section. To do this, we iterate over the traversal in reverse order and maintain the nodes we've gone over in a DSU.

However, the DSU we use for this algorithm is going to be a little different. We unite nodes as usual, but the find function differs.

Say xx is the root of the component we're calling find on. The node we're calling find on happens to be x, then we return x as usual. However, if it's some other node, then we return a node with the minimum sdom that lies on the path from uu to xx.

To process node uu we iterate over all nodes vv that have an edge directed towards it. If vv comes before uu in the preorder traversal, then vv is an ancestor of uu and would not have been processed till now. In that case, find(v) would return vv itself.

If not, then find(v) would return a node xx lying on the path from vv to the root in its DSU component with the smallest sdom.

If you're still a bit confused by this explanation, psuedocode for it is located on slide 33 of the Princeton slides given at the start of this module.

Computing rdom\texttt{rdom}

The rdom of a node is the node with the sdom that comes earliest in the traversal. Since this reduces to finding the minimum of a value along a certain path in a tree, we can implement this using an augmentation of binary jumping.

Implementation

Time Complexity: O((N+M)logN)\mathcal{O}((N+M) \cdot \log N)

C++

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <functional>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;

Cycles

Focus Problem – try your best to solve this problem before continuing!

Explanation

The problem asks as to find the an intersection node of all cycles, if it exists.

First, let's remove the nodes that don't belong to any cycle. To todo this, we can recursively remove the nodes without any outgoing edge. By "recursively," we mean that after finishing with a node we can check its parents to see if the parents have no outgoing edges as well.

Now our graph is basically a bunch of cycles. Assuming that the intersection of all cycles is not empty, we reduce the cycles node by node. The last node standing is be the intersection.

Implementation

Time Complexity: O(N)\mathcal{O}(N)

C++

#include <functional>
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
StatusSourceProblem NameDifficultyTags
CFHard
KattisHard

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!