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