【題解】TIOJ 1137 . 4.收費站設置問題

#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";
        }

    }
}