단절선

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

 

<소스 코드>

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int v, e;
 
vector<int> graph[100004];
// dfs 탐색 순서를 visited에 저장
int visited[100004];
vector<pair<int, int>> ans;
 
// 0, start, 1이 들어온다
int dfs(int parent, int start, int order) {
    int tmp = order;
    visited[start] = order;
 
    for (int i = 0; i < graph[start].size(); i++) {
        int next = graph[start][i];
        // 부모 노드로 돌아가는 경우는 무시
        if (parent == next)
            continue;
 
        // 아직 방문하지 않은 노드
        if (visited[next] == 0) {
            int next_order = dfs(start, next, order + 1);
            // next_order가 visited[start] 보다 크면
            // 노드를 방문하고 나서 못돌아온다는 의미
            // 즉, 브리지이다.
            if (next_order > visited[start]) {
                ans.push_back(make_pair(min(start, next), max(start, next)));
            }
 
            // 재귀를 나오면서 
            tmp = min(tmp, next_order);
        }
        // 방문된 노드라면 방문 순서 갱신
        else {
            tmp = min(tmp, visited[order]);
            continue;
        }
    }
    return tmp;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> v >> e;
    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    // 오름차순으로 그래프 정렬
    for (int i = 1; i <= v; i++)
        sort(graph[i].begin(), graph[i].end());
 
    for (int i = 1; i <= v; i++) {
        if (visited[i] == 0)
            dfs(0, i, 1);
    }
 
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (int i = 0; i < ans.size(); i++) {
        int s = ans[i].first;
        int e = ans[i].second;
        cout << s << ' ' << e << '\n';
    }
}