TIOJ 2050 尋找關節點 EXTREME

給一張

$N$ 點

$M$ 邊的圖，求有幾對

$a<b$ 滿足把節點

$a,b$ 拔掉之後整張圖不連通。

會錯的作法

有些人會隨便做三棵不共邊的生成森林，例如一開始開三個 DSU 各自維護一個生成森林，然後對於每條邊，找一個兩端點不連通的森林把它加進去，然後對這三個森林聯集起來的圖做這個問題。

但這是錯的，反例如下：

這整張圖是點三連通的，因此答案應該要是 0。然而，紅綠藍三種邊各自是一棵生成樹，只留下這三個生成樹的圖（少了 2-7 和 6-11 兩條邊）上，很明顯的 1 會是關節點。

對的作法

正確的作法是，先跑兩次 BFS 找出兩個不相交生成森林（第一棵一定是生成樹，拔掉第一棵後不連通的話第二棵會是森林），最後再隨便找一個生成森林（可以是任意的，只要三個森林不共邊就好）。這三個森林疊起來後做這個問題就是正確的了。

為什麼這是對的呢？假設原本的圖是

$G$，我們新蓋的圖是

$G^{\prime }$，我們要證明對於任兩個相異節點

$u,v$，把它們從兩張圖上拔掉之後，

$G$ 會不連通 iff

$G^{\prime }$ 會不連通。

因為

$G^{\prime }$ 是

$G$ 的子圖，所以當然

$G$ 不連通

$G^{\prime }$ 就也不會連通了。接下來，我們假設

$G^{\prime }$ 不連通，但

$G$ 是連通的，這代表圖會長得像這個樣子：

在拔掉

$u,v$ 之後，

$G^{\prime }$ 可以分成兩個互不連通點集

$C_1,C_2$（它們內部不一定連通，反正就是分成兩堆互不連通），不過在

$G$ 裡面，

$C_1,C_2$ 之間會有一條邊（下面那條虛線）連接

$C_1,C_2$ 讓它們保持連通。

考慮我們的兩個 BFS 生成森林，這兩次 BFS 都不會經過那條虛線，因此在

$C_1$ 和

$C_2$ 之間走肯定得經過

$u,v$。不失一般性，假設在第一個 BFS 裡，

$u$ 是先被走到的點，且起點是

$u$ 或是在

$C_1$ 裡，我們知道當

$u$ 被從 queue 裡 pop 的時候，

$C_2$ 的任何點都是 unvisited 的，因為走到

$C_2$ 一定要經過

$u,v$，但這是

$u$ 才正要被 pop、

$v$ 要不還在 queue 裡，不然根本就還 unvisited。所以，pop

$u$ 之後，BFS 就會去走所有從

$u$ 到

$C_2$ 的邊，並把它們加入第一個 BFS 生成森林中。要是

$u,v$ 之間有邊，此時也會被加進這個生成森林裡頭。

在第二次 BFS 的時候，

$u$ 到

$C_2$ 的邊被全拔了，所以

$v$ 是

$C_1$ 與

$C_2$ 之間的必經之路。為了方便敘述，接下來我們不考慮拔掉第一個生成森林後，和

$v$ 不連通的部分。第二次 BFS 時，無論起點在

$C_1,C_2$ 的哪一個，走到

$v$ 的時候，另一側的點一定是全部 unvisited，所以

$v$ 到其中一側的邊也會在這裡被全部拔掉。

所以，前兩個生成森林會拔掉（也就是包含）的邊有：

• $u$ 到
  $C_1,C_2$ 其中一側的全部邊
• $v$ 到
  $C_1,C_2$ 其中一側的全部邊
• $(u,v)$

因此，拔掉前兩個生成森林後，

$C_1,C_2$ 是完全不能透過

$u,v$ 走到對方的，能連接兩邊的道路只剩下直接連接兩側的邊，而第三個生成森林應該要包含這條邊，和

$G^{\prime }$ 不包含它的前提矛盾。

這樣，我們就證明了拔掉

$u,v$ 後，

$G$ 連通 iff

$G^{\prime }$ 連通。

後話

之所以要用 BFS，是因為 BFS 會有「把通往沒走過的地方的邊全部走一走」的性質，因為我們是要拆點，多個連在同一個點上的邊其實對連通性沒有太大的貢獻，而我們要做多個生成森林當然是希望更多座森林可以包含更多連通性的資訊。BFS 的這種性質在 2024 初選 pE 的 twpca 公布的題解中有被用到。

有趣的是，如果今天問題是拔兩條邊，那做三棵任意不相交生成森林都是好的，原理很簡單，如果拔掉某兩條邊後，

$G^{\prime }$ 會分成兩個互不連通區域

$C_1,C_2$，這意味著在

$G$ 之中，

$C_1,C_2$ 之間還有另一條邊，也就是這兩個區域之間至少有三條邊，第三條邊應該也要在三個生成森林之中才對。