略譯

原題目連結

給你一個有向圖，任兩點間至多有一條路，它可能是單行道或雙向道，
問你此圖是否任給兩點 a, b，都一定存在一點路徑能從 a 走到 b

題解

從題目定義來看，即是求此圖的最大強連通子圖是否就是自己；
即求 SCC 個數是否為 1

點最多到 2000 應該是不太能 floyd-warshall
從每個點出發做 Dijkstra 的複雜度也要 nm + nn log n

SCC 那些依賴於 DFS 的 n+m 複雜度比較合理

實作提示

• 無