[알고리즘] 단절선(bridge or cut edge)

단절선이란 무방향 그래프에서 해당 간선을 제거했을 때 그래프가 두 개 이상으로 나누어질 때 그 간선을 단절선이라고 합니다.

 

단절선은 단절점을 구하는 것과 유사합니다.

https://seokjin2.tistory.com/87

[알고리즘] 단절점(Articulation Points or Cut Vertices)

정점 A에서 부모 노드를 제외한 자식 노드들이 역방향 간선(backward edge)을 통해서 정점 A에 갈 수 없고 정점 A보다 위에 있는 선조로 갈 수 없으면 정점 A는 단절점이 됩니다.

 

단절점과 다른 점은 다음 두 가지입니다.

1. 루트가 빠졌다.

2. low > visited[A] (등호가 빠졌다) 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
 
using namespace std;
 
vector<int> adj[100001];
int visited[100001];
vector<pair<int, int> > cutEdge;
 
int v, e;
int num = 1;/*정점 A가 우회로를 통해서 갈 수 있는 가장 빠른 정점을 리턴*/
int dfs(int A, int parent) {
    visited[A] = num++;
    int ret = visited[A]; //처음엔 자기 자신이 최상위 노드
 
    for (auto& next : adj[A]) {
        if (next == parent) continue; //부모를 제외
        if (visited[next]) {
            ret = min(ret, visited[next]); // 우회로 갱신
            continue;
        }
 
        int low = dfs(next, A); // 자식 노드가 우회로를 통해서 갈 수 있는 가장 빠른 정점
 
        if (low > visited[A]) {//자식 노드가 정점 A와 정점 A보다 위에 있는 선조로 갈 수 없으면
            cutEdge.push_back({ min(A, next), max(A, next) }); //단절선
        }
        ret = min(ret, low); //정점 A가 갈 수 있는 선조 업데이트
 
    }
    return ret;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> v >> e;
    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
 
    for (int i = 1; i <= v; i++) {
        if (!visited[i]) dfs(i, 0);
    }
    sort(cutEdge.begin(), cutEdge.end());
 
    cout << cutEdge.size() << '\n';
    for (auto e : cutEdge) {
        cout << e.first << " " << e.second << '\n';
    }
    return 0;
}
 

<백준 문제>

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

11400번: 단절선