URAL 1691 - Algorithm Complexity

題目:
給出一個有向圖, 設 F(N) 為由 S->T 長度為 N 的 walk 的數目, 問是否存在一非負整數 k 和常數 C 使得 F(N) <= CN^k
Input: Graph, S, T
Output: k 的最小可能值


題解:
題目十分technical, 其實是說 S->T 的 walk 的數目是否能寫成 N 的多項式 (有點像big-O 的定義), 即 F(N) = O(N^k)
仔細想, 如果不能的話其實就是指數式, 即 F(N) = O(c^N)

在甚麼情況下會變成exponential呢? 首先想到的是如果每步都有多於1種選擇, 咁就變左c^k, 如 sample 2
然後又想甚麼情況才是N², N³ 等, 就會發現就是把 N 步「分配」到不同的環中, 即 C(N,M) = O(N^M)

所以, 先對圖做SCC
每個SCC可以分為數類:
1. 只有一個node
2. 一個簡單cycle
3. 以上皆否

明顯地, 如果S->T 能路過 type 3 的SCC, F(N) 就即刻變左 exponential
剩下的, 便是在縮點後的DAG中找 S->T 路過最多 type 2 的 path, 做 memorization dp 即可

怎樣判斷是type 2 還是 type 3 呢? 只要在該SCC中比較一下 |V| 和 |E|

還有URAL的stack size很細, 100000 個 node 做一次 dfs 都 stack overflow
解決方法: 我將由 1->n 改為 n->1 就過了..