단절선 [BOJ 11400]

단절선 [BOJ 11400] (P5 & Class 6)

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

11400번: 단절선

단절선이란?

 

하나의 컴포넌트로 구성된 무방향 그래프에서 특정 간선을 제거했을 때 두 개 이상의 컴포넌트로 나누어지는 간선

 

빨간색 간선들이 단절선

 

DFS Spanning Tree

 

단절점을 구하는 알고리즘과 상당히 비슷하다.

DFS Spanning Tree에 대한 기본적인 내용은 단절점 글을 참고!

https://unorderedmap.tistory.com/3

단절점 [BOJ 11266]

DFS Spanning Tree

그래프를 DFS Tree로 변환 후

- 트리에도 존재하는 간선 : tree edge

- 트리의 자손-조상 사이 간선 : back edge

- 그 외 간선 : cross edge

위 그림의 검은색 간선은 모두 tree edge, 파란색 간선은 back edge, 빨간색 간선은 cross edge이다.

 

Idea Motivation

 

tree edge가 아닌 간선을 제거해도 모든 그래프는 tree edge들로 연결되어 있다.

= tree edge만 단절선이 될 수 있다!

이에 따라 단절선의 후보를 어떤 정점 v와 그의 자식 노드 i를 이은 간선 (v, i)로 표현할 수 있다.

(v, i)가 단절선이라는 것은 v의 자손들 중에서는 v를 거치지 않고 v 이전에 방문했던 점에 갈 수 없다는 것이다.

 

구현

 

단절점 알고리즘과 매우 유사하다.

아래는 BOJ 11400번에 맞게 구현된 코드이다.

 

#include <bits/stdc++.h>
#define SIZE 100001
using namespace std;
/*
g : 인접리스트
ord[i] : i번 정점의 DFS 방문 순서
par[i] : i번 정점의 부모 노드
low[i] : i번 정점을 루트로 하는 서브트리에서 간선 하나만 거쳐서 갈 수 있는 정점 중 가장 작은 low 값
ret : 단절선을 저장하는 set
*/

vector<int> g[SIZE];
set<pair<int, int> > ret;
int par[SIZE], ord[SIZE], low[SIZE], t;
void dfs(int v)
{
    ord[v]=low[v]=++t;
    for (int i : g[v]) if (i!=par[v]) {
        if (!ord[i]) {
            par[i]=v;
            dfs(i);
            if (low[i]>ord[v]) ret.insert(make_pair(min(i, v), max(i, v)));
            low[v]=min(low[v], low[i]);
        }
        else low[v]=min(low[v], ord[i]);
    }
}
int main()
{
    int N, M, s, e, i;
    scanf ("%d %d", &N, &M);
    while (M--) {
        scanf ("%d %d", &s, &e);
        g[s].push_back(e);
        g[e].push_back(s);
    }
    for (i=1; i<=N; i++) if (!ord[i]) dfs(i);
    cout << ret.size() << endl;
    for (auto i : ret) printf("%d %d\n", i.first, i.second);
}

 

아래 블로그를 참고하여 공부했다.

https://justicehui.github.io/hard-algorithm/2019/01/06/bridge/