11400번 단절선

https://www.acmicpc.net/problem/11400

단절선의 핵심은 그림을 참고.

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 100001
#define INF 2e9
 
int dfn[Max], low[Max], par[Max], V, E, number;
vector<int> v[Max];
vector<pair<int, int> > bcc;
 
// 정점 x와 x의 자식 노드들 중 x와 x의 부모인 parent로 직접 연결된 간선을 이용하지 않고,
// 도달할 수 있는 정점 중 가장 먼저 dfs 함수가 방문한 정점을 반환
int dfs(int x, int parent)
{
    dfn[x] = ++number;
 
    int ret = dfn[x];
 
    for (auto next : v[x]) {
        if (next != parent) {
            if (!dfn[next]) {
                // low : 정점 x의 자식 노드가 갈 수 있는 노드 중 가장 일찍 방문한 노드
                int low = dfs(next, x); // next의 부모 = x
 
                if (low > dfn[x]) {
                    bcc.push_back({ min(x, next), max(x, next) });
                }
 
                ret = min(ret, low);
            }
            else {
                ret = min(ret, dfn[next]);
            }
        }
    }
 
    return ret;
}
 
int main()
{
    cin.tie(0);
 
    scanf("%d %d", &V, &E);
 
    int A, B;
    for (int i = 0; i < E; i++) {
        scanf("%d %d", &A, &B);
        v[A].push_back(B);
        v[B].push_back(A);
    }
 
    dfs(1, 0);
 
    sort(bcc.begin(), bcc.end());
 
    printf("%d\n", bcc.size());
    for (auto i : bcc) {
        printf("%d %d\n", i.first, i.second);
    }
 
    return 0;
}