단절점 기본 문제

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

int n, m;
vector<int> adj[10'001];
int ord[10'001];
int idx = 1;

bool isCut[10'001];

int dfs(int cur)
{
    ord[cur] = idx++;

    int ret = ord[cur];
    int ccnt = 0;

    for(int nxt: adj[cur]){
        if(ord[nxt]){
            ret = min(ret, ord[nxt]);
            continue;
        }
        else{
            int low = dfs(nxt);
            ret = min(ret, low);
            ccnt++;
            
            if(ord[cur] != 1 && ord[cur]<=low) isCut[cur] = true;
        }
    }
    if(ord[cur] == 1 && ccnt>=2) isCut[cur] = true;

    return ret;
}

signed main()
{
    FASTIO;
    cin >> n >> m;
    for(int i = 0; i<m; i++){
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    for(int i = 1; i<=n; i++){
        if(ord[i]) continue;
        idx = 1;
        dfs(i);
    }

    vector<int> ans;
    for(int i = 1; i<=n; i++){
        if(isCut[i]) ans.push_back(i);
    }

    cout << ans.size() <<"\\n";
    for(int e: ans) cout << e <<" ";
    
    return 0;
}