[백준] No.11400 - 단절선 (C++, Bridge)

문제

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

11400번: 단절선

 

 

풀이

 

solved.ac 난이도: Platium 5

 

이전 문제에서 단절점/절단점(무향 그래프에서 해당 점과 인접한 간선들을 모두 지웠을 때 그래프가 두 개 이상의 컴포넌트(서브 그래프)로 나뉘는 정점)에 대해서 다루었다.

이번에는 무향 그래프에서 간선을 지웠을 때 그래프가 두 개 이상의 컴포넌트로 나뉘는 간선인 절단선/단절선(Bridge / Cut edge)에 대한 문제이다.

 

사실 절단점을 찾는 코드를 조그만 변형 하면 쉽게 구현할 수 있다.

아래의 그래프에서 r 정점부터 방문을 시작하는 경우

간선 u-v가 절단선이 되기위해서는 v의 서브 트리에서 u나 u의 조상으로 가는 간선이 없어야 한다.

 

하지만 v에서는 u의 조상인 r로 가는 간선이 존재한다. 

따라서 u-v를 제거하여도 그래프가 두 개 이상의 컴포넌트로 나누어지지 않는다.

 

r-u의 간선의 경우도 u의 서브 트리에서 r자신으로 가는 간선이 존재하기 때문에 r-u를 제거하여도 그래프는 나뉘지 않는다.

즉, DFS로 방문하는 트리 간선(DFS 스패닝 트리 간선)을 제외한, 이미 방문한 노드로의 역방향 간선이 존재하는지를 확인하면 된다.

 

 

절단선을 구하는 코드는 절단점을 구하는 코드와 거의 비슷하게 구현하였다.

 

vector<vector<int>> adj;
vector<int> visited_order;
vector<pair<int,int>> bridge;
int order =0, bridge_cnt=0;
 
int FindCutVertex(int now_idx, int parent_idx){
  visited_order[now_idx] = ++order;
  
  int min_order = visited_order[now_idx];
  int subtree_min_order,next_idx;
  int a,b;
 
  for(int i=0; i<adj[now_idx].size() ; ++i){
    next_idx = adj[now_idx][i];
    if(visited_order[next_idx] == -1){
      subtree_min_order = FindCutVertex(next_idx, now_idx);
      
      if(subtree_min_order > visited_order[now_idx]){
        a=now_idx; b = next_idx;
        if(a > b) swap(a,b);
 
        bridge.push_back(make_pair(a,b ));
        bridge_cnt++;
      }
        
      min_order = min(min_order, subtree_min_order);
    }else{
      if(next_idx != parent_idx)
        min_order = min(min_order, visited_order[next_idx]);
    }
  }
 
  return min_order;
}

 

 

큰 차이점이 있다면 루트의 예외처리가 존재하지 않고

서브 트리에서의 최소 방문 순서 값이 현재 정점(now_idx)의 방문 순서보다 큰 경우

subtree_min_order > visited_order[now_idx]

즉, 하위 노드들이 now_idx나 now_idx의 조상과 연결되지 않은 경우만 해당 간선이 절단선이 된다.

 

이를 위해 now_idx의 부모 노드 parent_idx는 방문한 값이라도 visited_order[parent_idx]에는 접근하지 않는다.

부모 노드의 visited_order를 min_order와 비교하여 작은 값을 min_order에 넣게 된다면

부모 노드는 항상 now_idx보다 visited_order가 작기 때문에 min_order는 부모의 visited_order이하의 값만 가지게 된다.

이런 경우 절단선의 조건인 subtree_min_order > visited_order[now_idx]는 어떠한 경우에도 성립하지 않게 된다.

따라서 방문한 노드라면 parent노드가 아닌 경우만 min_order와 값을 비교해주자.

 

 

 

 

참고 서적: 알고리즘 트레이닝(안티 라크소넨 저)

 

 

코드