URAL 1557 - Network Attack

題目一句講完:
給出一個無向圖 G (可以有重邊/自環), 問有多少種方法 remove 2 條 edge 使得 G 變成 disconnected

一開始從 build BCC 的方向想, 可分為兩個 case: remove 一條 bridge + 任意, 以及在同一個 BCC 內 remove 兩條
不過想不到怎樣做 case2, 所以放棄了
後來想到可以用 DFS tree, 因為 tree 比較容易處理

先找出 G 的任意一棵 DFS tree
首先, 要使得 G disconnect 的話至少要 remove 一條 tree edge, 這樣就限制了很多可能性
以及, DFS tree 的其中一個特性是沒有 cross edge

Case 1: remove tree edge + remove back edge

很簡單, 只要記錄 subtree 的連通性便可以
Compute dp[x][y] = x 的 subtree 中有多少條 back edge 連到 y
便可以知道 x 的 subtree 有沒有連到外面, 如果是 0 條 edge 或 1 條 edge 就有方法做成 disconnect

Case 2: remove tree edge + remove tree edge

首先再分成 2 個情況: 兩條 tree edge 有沒有 ancestor 關系
如果沒有就很簡單, 做法和 case 1 十分類似

如果有的話則比較麻煩, 如圖, 紅色是想 remove 的 edge, 現要判斷綠色部份是否有連到藍色部份
而且要在 O(1) 內判斷
其實可以改變一下 dp[][] 的定義, 利用沒有 cross edge 的特性, 可知 x 的 subtree 只會連到 x 的 ancestor
dp[x][y] = x 的 subtree 中有多少條 back edge 連到 x 的第 y 層 ancestor
再使用 partial sum, 則可快速判斷

總時間為 O(N²+M)