단절선을 설명하기 전에 단절점에 대해 모른다면
이 글 을 먼저 읽어야 한다.

단절선이란?

단절선이란 단절점과 유사하다.
어느 한 선을 제거했을 때 그래프가 여러개로 나누어지는 선을 단절선이라 한다.

단절선 어떻게 찾을까?

단절점과 굉장히 비슷한 것에서 알 수 있듯이 찾는 방법도 거의 같다.
다만 다른 점이 3가지가 있다.

• 부모 정점은 발견 시간 갱신 대상이 아니다.
• low >= discovered[now]에서 =이 빠진다.
• 루트 노드의 단절선을 자식의 수로 판별하지 않는다.

왜 그런지는 아래 그림을 보며 생각해보자

단절선이 될 수 있는 건 1-2 간선이다.
위 그림에 표시된 화살표 숫자는 단절점을 구하는 기준으로 쓴 것이다.
단절점 기준으로 보면 1-2 간선과 2-3 간선이 단절선이 된다.
그래서 단절선을 구하기 위해서는 단절점과는 다른 위 2 조건이 필요한 것이다.

단절선 찾기 예시

이제 실제 코드가 돌아가는 방식으로 단절점을 어떻게 찾는지 살펴보자
주의 아래 설명은 이해를 위해 실제 코드가 돌아가는 방식과 100% 같지않음

1. 루트노드인 1번에서 DFS 탐색을 시작한다.

2번 3번 … 쭉 거쳐서 9번 노드를 7번째로 방문한다.

2. 9번에서 자신과 인접한 정점 중 자신보다 탐색시간이 빠른 정점을 살펴본다.

4번째로 방문한 4번이 있다.

3. 4를 9번 노드가 자신의 값으로 가지고 10번 노드에게 리턴해준다.

• 자신의 값이라는 건 자기가 어디까지 갈 수 있는지 저장한 것으로 탐색시간을 저장한 것과는 별개다.

4. 10번 노드는 9번으로부터 4를 돌려받고 자신의 탐색시간인 6보다 큰지 본다.

4가 더 작기 때문에 아무것도 하지 않고 자신의 값만 4로 갱신한다.

5. 11번 노드를 방문한다.

11번에서 연결된 노드는 10번 뿐이고 자신의 방문순서인 8을 저장하고 10번으로 리턴해준다.

6. 10번에서 리턴값 8을 받아 자신의 탐색시간인 6보다 큰지 본다.

8이 더 크기 때문에 10-11 간선을 단절선으로 판별한다.
10번이 자신의 값 4를 8번 노드로 리턴한다.

7. 8번은 4를 받고 자신의 탐색시간인 5와 비교한다.

5보다 작기 때문에 8번은 자신의 값을 4로 갱신하고 4번 노드로 리턴해준다.

8. 4번 노드가 8번에게 받은 4를 자신의 탐색시간인 4와 비교한다.

4로 동일하기 때문에 아무것도 하지 않는다.
4번 노드가 2번하고 연결되어 있기 때문에 자신의 값을 2로 갱신한다.
-> 사실 위 과정은 DFS탐색을 하며 4번에 도착했을 때 일어나는 일이지만 이해를 위해 지금 설명
4번이 자신의 값인 2를 3번 노드에게 리턴한다.

9. 3번 노드가 4번에게 받은 2를 자신의 탐색시간인 3과 비교한다.

3보다 작기 때문에 자신의 값을 2로 갱신하고 2번 노드에게 리턴한다.

10. 2번 노드가 3번에게 받은 2를 자신의 탐색시간인 2와 비교한다.

2로 동일하기 때문에 아무것도 하지 않는다.

11. 5번을 거쳐 6번 노드를 탐색한다.

6번에서 탐색할 노드가 없기 때문에 자신의 탐색순서 10을 리턴한다.

12. 5번 노드가 6번에게 받은 10를 자신의 탐색시간 9와 비교한다.

10이 더 크므로 5-6 간선을 단절선으로 판별한다.

13. 7번 노드를 탐색한다.

7번에서 탐색할 노드가 없기 때문에 자신의 탐색순서 11을 리턴한다.

14. 5번 노드가 7번에게 받은 11를 자신의 탐색시간 9와 비교한다.

11이 더 크므로 5-7 간선을 단절선으로 판별한다.
5번 노드가 자신의 탐색시간인 9를 리턴

15. 2번 노드는 5번에게 받은 9를 자신의 탐색시간 2와 비교한다.

9가 더 크므로 2-5 간선을 단절선으로 판별한다.
2번 노드가 자신의 탐색시간인 2를 리턴

16. 1번 노드는 2번에게 받은 2을 자신의 탐색시간 1과 비교한다.

2가 1보다 크므로 1-2를 단절선으로 판별

위에 말한 것처럼 실제 코드와 다른 점이 있다.
자신의 값을 갱신 하는 것은 DFS를 탐색할 때 자신이 이미 방문한 정점을 대상으로 갱신한다.
그러므로 예를 들어 4번 노드는 이미 DFS 과정에서 4번째로 방문했을 때 2로 값이 갱신된다.

코드

코드는 백준 11400번 - 단절선을 기준으로 작성했다.

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int, int>P;
int v, e, cnt, discovered[100001];
vector<P>res; // 결과 간선을 저장할 벡터
vector<vector<int>>arr;

int dfs(int now, int parent) {
	discovered[now] = ++cnt;
	int num = discovered[now];
	
	for (int i = 0; i < arr[now].size(); i++) {
		int next = arr[now][i];

		if (next == parent) // 부모 정점으로 가는 간선은 제외
			continue;

		if (discovered[next] == 0) {
			int low = dfs(next, now);
			num = min(low, num);
			if (low > discovered[now]) // 현재 발견시간보다 자식 노드의 발견시간이 늦을 때
				res.push_back({ min(now,next), max(now,next) });
		}
		else
			num = min(num, discovered[next]);
	}
	return num;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> v >> e;
	arr.resize(v + 1);
	for (int i = 0; i < e; i++) {
		int a, b; cin >> a >> b;
		arr[a].push_back(b);
		arr[b].push_back(a);
	}
	dfs(1, 0);

	sort(res.begin(), res.end());
	cout << res.size() << "\n";
	for (int i = 0; i < res.size(); i++)
		cout << res[i].first << " " << res[i].second << "\n";
	return 0;
}

시간복잡도

DFS 한번으로 끝나기 때문에 O(V + E)가 걸린다.