단절점이란?

단절점이란 굉장히 단순한 개념이다.
어떤 한 정점를 지운다고 가정했을 때 그래프가 여러개로 나뉜다면 단절점이다.
다른 말로는 그 정점이 없이는 모든 정점들을 한번에 방문할 수 없는 것이다.

단절점 어떻게 찾을까?

우선 단절점에 대해 이야기하기 전에 DST라는 것을 알아보자.
DST는 DFS Spanning Tree로 DFS의 방문순서를 통해 만든 트리이다.

위에서 본 그래프를 DST로 만든다면 아래와 같이 된다.

초록색 번호는 방문 순서를 적은 것이고 점선은 DSF탐색에 이용되지 않은 간선이다.

이제 이 DST를 이용해 단절점을 찾을 것이다.

비효율적인 방법

가장 쉽게 생각해볼 수 있는 방법은 노드를 하나씩 제거해보며
DFS로 모든 정점을 탐색할 수 있나 보는 것이다.
하지만 예상되듯이 엄청나게 비효율적이다.

시간복잡도를 생각해보면 DFS를 노드 수만큼 수행해야 하므로 O(V * (V + E))가 걸린다.
V^2이므로 노드의 수가 조금이라도 많아진다면 힘들어 보인다.

효율적인 방법

규칙은 두가지이다.

• 정점 A보다 늦게 탐색 되는 정점들에서 정점 A보다 먼저 탐색 되는 정점으로 가는 경로가 없는 경우 정점 A는 단절점이다.

• 루트 노드로 잡은 특정 노드의 자식 수가 2개 이상이면 단절점이다.

우선 두번째 규칙부터 살펴보자
위 그래프에서는 1번 노드가 루트인데 1번 노드가 없어진다고 그래프가 나뉘진 않는다.
하지만 만약 1번에서 시작하는게 아닌 2번 노드에서 시작하여 2번이 루트라고 하면
루트가 없어지면 그래프가 나뉘게된다.
여기서 알 수 있는 사실은 루트의 자식이 2개 이상이면 루트는 단절점이 될 수밖에 없다.

이제 첫번째 규칙을 보자
8번 노드를 보자 8번은 단절점이 될 수 있을까?
8번보다 늦게 탐색되는 노드는 10, 9, 11이다.
그런데 9번 노드에서는 4번 노드로 가는 간선이 존재한다.
8번 보다 늦게 탐색되는 9번에서 8번보다 빨리 탐색되는 4번으로 가는 길이 있는 것이다.
그러므로 8번은 단절점이 될 수 없다.

그럼 10번을 보자 10번보다 늦게 탐색되는 노드는 9와 11이다.
9번 같은 경우는 아까 봤듯이 4번으로 가는 경로가 존재하기 때문에
10번이 없어지더라도 그래프가 나뉘진 않는다.

하지만 11번을 보면 10번보다 빨리 탐색되는 노드로 갈 수 없다.
그렇기 때문에 10번이 없어진다면 그래프가 나뉘게 된다.
그러므로 10번은 단절점이 된다.

단절점 찾기 예시

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

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

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

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

6번째로 방문한 10번과 4번째로 방문한 4번이 있다.

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

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

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

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

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

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

6. 10번에서 리턴값 6을 받아 자신의 탐색시간인 6보다 크거나 같은지 본다.

6으로 동일하기 때문에 10번을 단절점으로 판별한다.
10번이 자신의 값 4를 8번 노드로 리턴한다.

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

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

8. 4번 노드가 8번에게 받은 4를 자신의 탐색시간인 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로 동일하기 때문에 2번 노드를 단절점으로 판별한다.

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

6번에서 인접한 5번 노드의 탐색시간인 9를 자신의 값으로 갱신 후 리턴

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

9로 같으므로 5번 노드를 단절점으로 판별한다.

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

7번에서 인접한 5번 노드의 탐색시간인 9를 자신의 값으로 갱신 후 리턴

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

9로 같으므로 5번 노드를 단절점으로 판별한다.
5번 노드가 인접한 노드 중 가장 작은 탐색시간인 2를 자신의 값으로 갱신 후 리턴

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

2로 같으므로 2번 노드를 단절점으로 판별한다.
2번 노드가 인접한 노드 중 가장 작은 탐색시간인 1을 자신의 값으로 갱신 후 리턴

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

값이 같지만 루트 노드이므로 자식 노드의 개수로 판별
자식 노드가 하나이므로 단절점이 아님

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

코드

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

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
49
50
51
52
53
54
55
56
57

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int v, e, cnt, discovered[10001]; // cnt - 방문 번호, discovered - 발견시간
bool res[10001]; // 노드가 단절점인지 저장하는 배열
vector<vector<int>>arr; // 그래프 저장

int dfs(int now, bool root) {
	discovered[now] = ++cnt;
	int num = discovered[now];
    // num은 인접한 노드 중 가장 발견시간이 빠른 노드를 저장했다가 리턴
	
	int child = 0; // 루트노드를 염두해 자식 수를 저장
	for (int i = 0; i < arr[now].size(); i++) {
		int next = arr[now][i];
		if (discovered[next] == 0) { // 방문이 안된
			child++;
			int low = dfs(next, false);
			num = min(low, num);
			if (!root && low >= discovered[now]) 
                // 루트 노드가 아니고 현재 노드의 발견 시간보다 자식 노드의 발견시간이 더 크거나 같다면
				res[now] = true;
		}
		else // 이미 방문했다면
			num = min(num, discovered[next]);
	}
	if (root && child > 1) // 루트이고 자식 개수가 2이상이면 단절점
		res[now] = true;
	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);
	}
	for (int i = 1; i <= v; i++) {
		if (discovered[i] == 0)
			dfs(i, true);
	}
	int resSum = 0;
	for (int i = 1; i <= v; i++) {
		if (res[i])
			resSum++;
	}
	cout << resSum << "\n";
	for (int i = 1; i <= v; i++) {
		if (res[i])
			cout << i << " ";
	}
	return 0;
}

시간복잡도

DFS 한번으로 끝나기 때문에 O(V + E)가 걸린다.
비효율적 방법인 V^2과는 엄청난 차이다.