【範例】圖的割點,DFS tree,low的意義
【題目敘述】https://tioj.ck.tp.edu.tw/problems/1137
#include <bits/stdc++.h>
using namespace std;
int T, n, m, a, b, dfn[10005], low[10005], idx;
vector <int> v[10005];
vector <int> ans;
void dfs(int x, int pre){
idx++;
dfn[x] = idx;
low[x] = idx;
int cnt = 0;
bool flag = false;
for (int i:v[x]){
if (i == pre) continue;
if (dfn[i]) low[x] = min(low[x], dfn[i]);
else{
cnt++;
dfs(i, x);
low[x] = min(low[x], low[i]);
if (low[i] >= dfn[x]) flag = true;
}
}
if (x == 1 && cnt > 1) ans.push_back(x);
else if (x != 1 && flag) ans.push_back(x);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while (T--){
cin >> n >> m;
for (int i = 1; i <= n; i++){
v[i].clear();
dfn[i] = 0;
low[i] = 0;
}
for (int i = 0; i < m; i++){
cin >> a >> b;
if (a == b) continue;
v[a].push_back(b);
v[b].push_back(a);
}
ans.clear();
idx = 0;
dfs(1, 0);
sort(ans.begin(), ans.end());
if (!ans.size()) cout << "0\n0\n";
else{
cout << ans.size() << "\n";
for (int i:ans){
cout << i << " ";
}
cout << "\n";
}
}
}