cactus graph
cactus graph
directed cactus graph
有向圖上，每條邊隸屬於恰好一個有向環。另一種說法：許多有向環，相互銜接成樹狀，接縫恰好是一點。
要判斷一張有向圖是不是仙人掌，原理就跟判斷關節點的方法相同。
使用 DFS ，會遇到三種情形：
一、 (i, j) 是 cross edge 或 forward edge：
tree edge 和 back edge 剛好構成仙人掌全部的邊，
不會有 cross edge 與 forward edge。
如果有，就表示不是仙人掌。
實作時，可利用 DFS stack 判斷，
如果 j 不在 stack 又已經拜訪過（也就是 j 已經從 stack 彈出），
則表示 (i, j) 一定是 cross edge 或 forward edge。
二、 (i, j) 是 back edge：
如果從 i 就已經有路可以走回到 i 的祖先（也是會經過其他的back edge），
此時 j 又走回到 i 的祖先，表示環重疊，不是仙人掌。
範例一：12 23 34 45 56 62 53! // i = 5 and j = 3
範例二：12 23 34 45 51! 53! // 怎麼好像在寫棋譜...
實作時，累加 i 回到祖先的路有幾條，只能是恰好一條。
可利用關節點演算法的原理，記錄 i 可到達的最高祖先。
三、 (i, j) 是 tree edge：
與 2. 的概念很像，不過要在 DFS 的回溯階段才能判斷。
如果從 i 就已經有路可以走回到 i 的祖先，
此時 j 又有路走回到 i 的祖先，表示環重疊，不是仙人掌。
範例一：12 23 34 45 56! 67! 72! 58! 89! 91! // i = 5 and j = 8
範例二：12 23 34 45 51! 58! 89! 91! // 同上
實作時，累加 i 回到祖先的路有幾條，只能是恰好一條。和（二）一起累加。
可利用關節點演算法的原理，記錄 i 可到達的最高祖先。
DFS 結束之後，
最後要判斷 DFS 是否能順利走到圖上所有點。
附註：樹根不必走到祖先，要當作例外處理。可以選定任何一點作為樹根。
UVa 10510 ICPC 3514 4045