【題解】[ZJOI2007]最大半連通子圖

[ZJOI2007]最大半連通子圖

\(\text{Solution:}\)

首先考慮何時滿足題目中所說的最大半連通子圖。

先把強連通分量縮起來應該是毋庸置疑的一步了。考慮如何從一個強連通分量來拓展到半連通分量。

推論1：如果一張縮完點的圖是半連通圖，那麼它的拓撲序一定唯一。

\(Proof:\) 假定拓撲序不唯一，也就是在 \(bfs\) 的過程中，隊列同時存在了兩個點，那麼這兩個點必然是無法互相到達的。證畢。

那麼，有了這麼一個推論，我們就可以考慮如何解題了：先考慮如何計算最大的節點數。我們縮完點之後令強連通分量的 \(siz\) 為其連通塊大小，問題就轉化為了有向圖求最長鍊了。

那麼方案數咋求？考慮設 \(f_i,g_i\) 分别表示到點 \(i\) 的最大節點數和方案數。如果更新了 \(f\) 就把 \(g\) 置為 \(0,\) 否則直接累加。比目前 \(f\) 小的就可以跳過了。

注意邊的去重。可以去枚舉原圖每次清空數組做到無 $\log $ 判重，但是筆者比較懶直接上 <code>map</code> 了。

注意，計算 \(siz\) 不能取模，更新 \(g\) 的時候要取模。