..
邊雙連通圖定向為強連通圖
一個邊雙連通圖一定能定向為強連通圖，反之，一個強連通圖将邊無向化會得到一個邊雙連通圖。
一開始我以為遮是一個不太顯然的結論，後面發現是因為對 Tarjan 算法求 SCC/BCC 完全不理解，其實祇要通過 Tarjan 算法便能完成構造性證明，求遮兩個東西的方法是一样的。
所以，祇需任選一個點開始 DFS，父親向兒子連有向邊，若有反祖邊，則由 DFN 序大的指向 DFN 序小的。最後得到的就是一個强連通圖。
一個邊雙連通圖一定能定向為強連通圖，反之，一個強連通圖将邊無向化會得到一個邊雙連通圖。
一開始我以為遮是一個不太顯然的結論，後面發現是因為對 Tarjan 算法求 SCC/BCC 完全不理解，其實祇要通過 Tarjan 算法便能完成構造性證明，求遮兩個東西的方法是一样的。
所以，祇需任選一個點開始 DFS，父親向兒子連有向邊，若有反祖邊，則由 DFN 序大的指向 DFN 序小的。最後得到的就是一個强連通圖。