Algorithm - Cut Edge (단절선)

개념

단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 

---

작동원리

DFS를 이용하여 정점이 몇 번째로 방문되는지 기록하고, 기록한 값 중에 최솟값을 반환한다. 

 

DFS를 통해 반환된 값들 중 자신보다 큰 값이 있으면 단절선이다.

(아직 방문하지 않았다는 뜻으로, 지금 보는 정점이 아니면 갈 방법이 없다는 뜻, 즉 지금 보는 간선을 제거하면 그래프가 분리된다.)

---

시간복잡도

DFS를 할 때 O(V + E)

---

문제

11400 단절선

www.acmicpc.net/problem/11400

11400번: 단절선

---

코드

#include <bits/stdc++.h>
using namespace std;

constexpr int NONE = -1;

int v, e;
vector<vector<int>> graph;

int order = 0;
vector<int> isVisited;
vector<pair<int, int>> ans;
int dfs(int index, int pre) {
    isVisited[index] = order++;

    int result = isVisited[index];
    for (int &next : graph[index]) {
        if (next == pre) {
            continue;
        }

        if (isVisited[next] == NONE) {
            int low = dfs(next, index);
            if (low > isVisited[index]) {
                ans.emplace_back(min(index, next), max(index, next));
            }

            result = min(result, low);
        } else {
            result = min(result, isVisited[next]);
        }
    }

    return result;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    cin >> v >> e;
    graph.resize(v + 1);
    while (e--) {
        int v1, v2;
        cin >> v1 >> v2;

        graph[v1].push_back(v2);
        graph[v2].push_back(v1);
    }

    isVisited.resize(v + 1, NONE);
    for (int i = 1;i <= v;++i) {
        if (isVisited[i] == NONE) {
            dfs(i, 0);
        }
    }

    cout << ans.size() << "\n";

    sort(ans.begin(), ans.end());
    for (auto &&p : ans) {
        cout << p.first << " " << p.second << "\n";
    }
}