Bridge (단절선)

단절점 문서를 먼저 보시는 것을 추천합니다.

아래의 코드는 단절선(https://www.acmicpc.net/problem/11400) 문제에 대한 코드입니다. 템플릿은 만들어주세요!

코드

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> g[100001];
vector< pair<int, int> > ans;
int discovered[100001], cnt;

int dfs(int parent, int node)
{
    discovered[node] = ++cnt;
    int ret = discovered[node], i;

    for ( i = 0; i < g[node].size(); i++ ) {
        int u = g[node][i];
        if ( parent == u ) continue;
        if ( discovered[u] )
            ret = min(ret, discovered[u]);
        else {
            int low = dfs(node, u);
            if ( low > discovered[node] )
                ans.push_back( make_pair(min(node, u), max(node, u)) );
            ret = min(ret, low);
        }
    }

    return ret;
}

int main()
{
    int v, e, a, b, i;

    scanf("%d%d", &v, &e);
    while(e--) {
        scanf("%d%d", &a, &b);
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(0, 1);

    sort(ans.begin(), ans.end());

    printf("%d\n", ans.size());
    for ( i = 0; i < ans.size(); i++ )
        printf("%d %d\n", ans[i].first, ans[i].second);
}

정리

• 단절점과 같은 개념이며, 소스가 비슷함
• 결국, 스패닝트리로 구성했을 때, 자식의 방문순서가 현재 노드의 방문순서보다 빠르면 우회경로가 있고 따라서 해당 간선은 단절선이 아니다.
• 단절점과 달리 루트에 대한 처리를 할 필요가 없다.

관련 문제

• 단절선: https://www.acmicpc.net/problem/11400

참고 자료

• 종만북 - 857 페이지
• http://bowbowbow.tistory.com/3