POI - 2018 - Bike Paths

Author: Neo Wang

Edit This Page

Table of Contents

ExplanationImplementation

Explanation

Notice that groups of intersections can form strongly connected components. Therefore, treat each component as a node with initial value equal to the size of the component. Since the resulting strongly connected components comp\texttt{comp} form a directed acyclic graph (specifically a tree, because of the "justness" from the problem statement), process the edges ee in reverse topographical order cc with the following relation where dp[i]\texttt{dp}[i] is the # of intersections that can be reached from component ii:

dp[comp[e]]=dp[comp[e]]+∑e∈radj[c]dp[comp[c]]:comp[c]≠comp[e]\texttt{dp}[\texttt{comp}[e]] = \texttt{dp}[\texttt{comp}[e]] +\sum_{e \in \texttt{radj}[c]} \texttt{dp}[\texttt{{comp}}[c]] : \texttt{comp}[c] \neq \texttt{comp}[e]

The final answer for intersection ii is dp[comp[i]]−1\texttt{dp}[\texttt{comp}[i]] - 1, since we exclude the starting intersection from the answer.

Warning!

This solution only works on a tree (and not a general DAG), because of over counting.

Suppose we have a graph with N=4N=4 nodes, and the edges

1 2
1 3
2 4
3 4

which correspond to the edges 1→2,1→3,2→4,3→41 \rightarrow 2, 1 \rightarrow 3,2 \rightarrow 4,3 \rightarrow 4.

A valid topographical sort could be in the order 4,2,3,14, 2, 3, 1, which would not work because node 44 is counted twice. Our calls would be as follows:

  • dp[4]=1\texttt{dp}[4] = 1
  • dp[2]=1+dp[4]=2\texttt{dp}[2] = 1 + \texttt{dp}[4] = 2
  • dp[3]=1+dp[4]=2\texttt{dp}[3] = 1 + \texttt{dp}[4] = 2
  • dp[1]=1+dp[2]+dp[3]=5\texttt{dp}[1] = 1 + \texttt{dp}[2] + \texttt{dp}[3] = 5

Evidently, dp[4]\texttt{dp}[4] is counted twice in dp[1]\texttt{dp}[1].

Implementation

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

C++

 Code Snippet: Benq Template (Click to expand)


/**
 * Description: Kosaraju's Algorithm, DFS twice to generate
 * strongly connected components in topological order. $a,b$
 * in same component if both $a\to b$ and $b\to a$ exist.
 * Time: O(N+M)
 * Source: Wikipedia
 * Verification: POI 8 peaceful commission
 */

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!

Join Forum