發表文章

目前顯示的是 11月, 2020的文章

[TIOJ] 2050. 尋找關節點 EXTREME

題目連結: https://tioj.infor.org/problems/2050 上次來這裡寫東西好像是超級久以前ㄌXD 貼一下昨天吃飯聽到的做法,但是我不會證明,求知道的人貼個 paper 給我 (。・∀・)ノ゙,只知道這是蔡孟宗教授在我高二那年二階講的算法。 這題重點是如何把一張圖的邊減少到 $O(N)$ 量級,但還是保持著一些必要的連通性。如果我昨天吃飯的時候沒聽錯的話,我們可以做 $k$ 次 BFS 來找出生成森林,每次找出來後就把它從原圖中拔掉,並記錄到我們最後要取的邊集中,如果要求雙連通分量的話,那 $k=2$ ,而像這題是某種三連通,所以 $k=3$。 所以這題就把邊減少到 $O(N)$ 量集後就可以拔掉每個點,跑一次 tarjan 找出所有其他割點,不過有一些小細節要注意一下,例如拔掉一條鍊的最邊邊兩個點不會讓圖變得不連通之類ㄉ。 &num;include <bits&sol;stdc&plus;&plus;&period;h> using namespace std&semi; const int N &equals; 2000 &plus; 5&semi; const int M &equals; 2000000 &plus; 5&semi; class BCC&lowbar;AP &lcub; &Tab;private&colon; &Tab;&Tab;int n&comma; ecnt&semi; &Tab;&Tab;vector<vector<pair<int&comma;int>>> G&semi; &Tab;&Tab;vector<int> bcc&comma; dfn&comma; low&comma; st&semi; &Tab;&Tab;vector<bool> ap&comma; ins&semi; &Tab;&Tab;void dfs&lpar;int u