[그래프] 단절선

작성일 | In

단절선이란?

하나의 컴포넌트(connected component)로 구성되어 있는 그래프에서 특정 간선을 제거할 때, 컴포넌트의 개수가 증가하는 간선을 단절선 이라고 합니다.
쉽게 말해, 어떤 간선을 제거했을 때, 그래프가 둘 이상으로 나뉘게 된다면 그 간선은 단절선입니다.


위 그림에서는 (1, 6), (6, 7)이 단절선이 됩니다.

Naive한 방법

단절선을 구하는 가장 간단한 방법은 단절점을 구하는 가장 간단한 방법과 유사합니다.
간선을 하나씩 없애보면서 컴포넌트가 증가하는지 확인해주면 됩니다. O(E*(V+E))만에 할 수 있습니다.

더 효율적인 방법을 알아봅시다.

DFS Tree를 이용한 방법


이 그래프의 dfs tree는 다음과 같습니다. 빨간색은 back edge, 파란색은 cross edge입니다.

위 그래프에서는 (1, 6)과 (6, 7) 간선이 단절선입니다.

dfs tree를 구성할 때, A번째로 방문한 정점을 V라고 합시다. 정점 V와 부모 정점 U를 잇는 간선이 단절선이 되기 위해서는 아래 조건을 만족해야 합니다.

  • 간선 (U, V)를 제외했을 때, 정점 V를 포함해 A번째 이후로 방문한 모든 정점에서 A번째 이전에 방문했던 정점에 갈 수 없어야 한다.

우회로의 개념에서 보면 이해가 쉽습니다. A번째 이후로 방문한 모든 정점에서 A번째 이전에 방문했더 정점에 갈 수 있다는 것은, A번째로 방문한 정점을 거치지 않아도 위로 갈 수 있음을 의미하므로 단절선이 아니게 됩니다.
추가로, 단절선은 Tree Edge에만 존재합니다.

단절선의 판별법을 다시 정의해봅시다.

  • 현재 정점 A와 자식 정점 B를 잇는 간선 (A, B)에서, A의 자손들 중 A를 거치치 않고 A 이전에 방문했던 정점에 갈 수 없다면 간선 (A, B)는 단절선이다.

단절선도 단절점과 마찬가지로 Tarjan’s Algorithm을 이용해 구현할 수 있습니다.

구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<int> g[100010];
int order[100010]; //발견 순서
int par[100010];  //부모
int low[100010]; //i를 루트로 하는 서브 트리에서 가장 위로 갈 수 있는 노드
vector<p> ans;
int t;

void dfs(int v){
	order[v] = t++;
	low[v] = t;

	for(auto i : g[v]){ //i : 다음에 갈 노드
		if(i == par[v]) continue; //내 부모 == 나 임면 스킵

		if(order[i] == 0){ //아직 발견이 안되었다면
			par[i] = v; //다음 노드의 붑모는 현재 노드
			dfs(i);

			if(low[i] > order[v]) ans.push_back({min(v, i), max(v, i)});
			/*서브 트리에서 위로 더 올라갈 수 없으면 단절점 확정*/

			low[v] = min(low[v], low[i]);
		}
		else low[v] = min(low[v], order[i]);
	}
}