단절선 (Bridge)

문제

그래프가 주어졌을 때, 단절선을 모두 구해 출력하는 프로그램을 작성하시오.

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

입력

첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다.

그래프는 항상 연결되어 있으며, 같은 간선이 두 번 이상 들어오는 경우는 없다. 또, A와 B가 같은 경우도 없다.

그래프의 정점은 1부터 V까지 자연수이다.

출력

첫째 줄에 단절선의 개수 K를 출력한다.

둘째 줄부터 K개 줄에는 단절선을 사전순으로 한 줄에 하나씩 출력한다. 간선은 “A B” 형식으로 출력해야 하고, A < B를 만족해야 한다. 같은 간선은 한 번만 출력하면 된다. 즉, “A B”를 출력한 경우에 “B A”는 출력할 필요가 없다.

예제 입력

예제 출력

2
1 6
6 7

문제 풀이

단절선 코드를 테스트하는 문제이다.

절단점 u대신 v를 찾고, parent랑 묶인 edge를 찾아서 풀었다.

답안 코드

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_V   100000+1
#define MAX_E   1000000

int V, E, a, b;

vector<int> adj[MAX_V];
int dfs_num[MAX_V];
int dfs_low[MAX_V];
int dfs_parent[MAX_V];
int dfs_count;

bool articulation_vertex[MAX_V];
vector<pair<int, int>> ans;

void dfs(int u){
    dfs_num[u] = dfs_low[u] = ++dfs_count;
    for(int i = 0; i < adj[u].size(); ++i){
        int v = adj[u][i];
        if (dfs_num[v] == 0){
            dfs_parent[v] = u;
            
            dfs(v);
            
            if (dfs_low[v] > dfs_num[u]) // 절단선
                articulation_vertex[v] = true;
            
            dfs_low[u] = min(dfs_low[u], dfs_low[v]);
        }
        else if(dfs_parent[u] != v){    // 이전 간선은 역방향 간선이 아님
            dfs_low[u] = min(dfs_low[u], dfs_low[v]);
        }
    }
}

int main(){
    scanf("%d %d\n", &V, &E);
    for(int i = 0; i < E; ++i){
        scanf("%d %d\n", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    for(int i = 1; i <= V; ++i)
        if(dfs_num[i] == 0)
            dfs(i);
    
    for(int i = 1; i <= V; ++i)
        if(articulation_vertex[i]){
            if(i < dfs_parent[i])
                ans.push_back(make_pair(i, dfs_parent[i]));
            else
                ans.push_back(make_pair(dfs_parent[i], i));
        }
    
    sort(ans.begin(), ans.end());
    
    printf("%d\n", ans.size());
    for(int i = 0; i < ans.size(); ++i)
        printf("%d %d\n", ans[i].first, ans[i].second);
    
    return 0;
}