11400번: 단절선

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


$O(n\lg n)$ // 알고리즘 자체는 O(n)이지만 출력시에 정렬을 해야하기 때문이다.

단절선 알고리즘을 구현해보자.
참고로 어떤 두 정점 사이에 간선이 2개 이상 존재하는 경우, 소스를 조금 수정해야 한다.

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
const int MAX_V = 1e5;
int v, e, t[MAX_V + 1];
vector<int> adj[MAX_V + 1];
vector<pair<int, int> > r;
void dfs(int h, int p, int d) {
    t[h] = d;
    for (auto it : adj[h]) {
        if (it == p) continue;
        if (!t[it]) {
            dfs(it, h, d + 1);
            if (t[it] == d + 1)
                r.push_back(h < it ? make_pair(h, it) : make_pair(it, h));
        }
        t[h] = min(t[h], t[it]);
    }
}
int main() {
    scanf("%d %d", &v, &e);
    for (int i = 0, x, y; i < e; i++) {
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1, -1, 1);
    sort(r.begin(), r.end());
    printf("%d\n", r.size());
    for (auto it : r) printf("%d %d\n", it.first, it.second);
    return 0;
}