[TIOJ] 1137. 4.收費站設置問題

題目連結: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>>st>>ed;
			graph[st].push_back(ed);
			graph[ed].push_back(st);
		}
		dfs(1,1,1);
		cout<<ap.size()<<'\n';
		if(!ap.empty()) for(auto i:ap)
			cout<<i<<' ';
		else cout<<0;
		cout<<'\n';
	}
	return 0;
}

void dfs(int x,int f,int d){
	low[x]=d;
	visited[x]=1;
	int child=0;
	for(auto i:graph[x]){
		if(i==f)continue;
		if(!visited[i]){
			dfs(i,x,d+1);
			child++;
		}
		low[x] = min(low[i], low[x]);
		if(low[i]>=d) ap.insert(x);
	}
	if(d==1 && child <= 1) ap.erase(x);
}