oToToT的code收藏區

題目連結: 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;p...

題目連結: http://tioj.infor.org/problems/1137 應該不難看出來題目就是在求一個點使得拔掉後會讓兩個區塊不連通，那這正好就是關節點。而關節點的求法是什麼呢？這裡採用tarjan的算法： 在以某一特定點DFS的情況下，會長出一個類似樹的部分，只不過有些邊會連回上面，也就是樹上不該有的邊，這裡稱其為「回邊」，而正常定義的樹上會有的邊，這裡稱其為「樹邊」。 接著，定義一種值$ low(x), x \in V$其中V為所有點的點集，low(x)為點x不透過連接自己的樹邊，所能到達的深度的最小值(往上最遠可以到哪)，仔細觀察後發現，當一個點p的小孩中，有一個點q的low值$ \leq $自己的深度，意即其必須透過p才能回到上面，那明顯p就會是一個關節點(因為拔掉p之後q就會與一些人不連通了)，不過特別注意一下根的部分，因為顯然所有人的low值都$ \leq $根的深度，但是根不一定關節點，細想一下後會發現根不是關節點的條件為他只有一個小孩的時候，那到這裡算法的架構就大概完整了。 至於low值維護的方式就是邊dfs邊用類似dp的方式維護即可了。 #include <bits/stdc++.h> using namespace std; #define N 10000 vector<int> graph[N+5]; int low[N+5]; bool visited[N+5]; set<int> ap; void dfs(int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t;cin>>t; while(t--){ ap.clear();fill(visited, visited+N+5, false); int n,m;cin>>n>>m; for(int i=0;i<m;i++){ int st,ed;cin>>s...