[그래프] SCC - Tarjan

작성일 | In

SCC를 구하는 또 다른 알고리즘인 Tarjan’s Algorithm을 알아봅시다.

작동 방식

타잔 알고리즘은 dfs tree상에서 두 가지 지표를 이용해 SCC를 구합니다.

  1. num[i] : i번 정점이 몇 번째로 방문한 정점인지를 저장합니다. (discovert time)
  2. low[i] : i번 정점을 루트로 하는 서브트리에서 간선 하나만 거쳐서 갈 수 있는 정점 중, 가장 작은 low값을 저장합니다.

사전 정보 구하기


예시로, 위 dfs tree에서 정점의 번호와 num값이 같다고 가정해봅시다.
low[7]은 7번 정점을 루트로 하는 서브트리에서 간선 하나만 거쳐 갈 수 있는 정점 중 가장 작은 low값을 의미합니다.
7에서는 3으로 갈 수 있고, 9에서는 4로 갈 수 있고, 10에서는 1로 갈 수 있고, 12에서는 2로 갈 수 있습니다.
그러므로 low[7]은 1이 됩니다.

low의 값을 구할 때, 두 가지의 경우가 있습니다. edge(u, v)가 tree edge라면, low[u] = min(low[u], low[v])입니다.
edge(u, v)가 back edge라면, low[u] = min(low[u], num[v])입니다.

num과 low를 구하는 코드를 먼저 작성해봅시다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int num[10101];
int low[10101];
bool visit[10101];
int cnt = 0;
vector<int> g[10101];

void dfs(int now){
	if(visit[now]) return;
	visit[now] = 1;
	num[now] = ++cnt;
	low[now] = cnt;
	for(auto nxt : g[now]){
		if(visit[nxt]) low[now] = min(low[now], num[nxt]);
		else{
			dfs(nxt);
			low[now] = min(low[now], low[nxt]);
		}
	}
}

SCC 뽑아내기

그래프를 하나 들고 오겠습니다.

dfs tree를 그리면서, num과 low를 구해줍시다.

dfs가 정점을 방문한 순서대로 나열해봅시다.
1(1, 1) - 4(2, 1) - 2(3, 1) - 3(4, 4) - 5(5, 5) - 6(6, 5)

dfs는 가장 먼저 6이 리턴됩니다. 그 다음은 5가 리턴이 되는데, 5는 num값과 low값이 같습니다. 5와 6은 같은 SCC에 속합니다.
그 다음으로는 3이 리턴됩니다. 3은 num값과 low값이 같기 때문에 3 하나만 같은 SCC에 속하게 됩니다.
다음으로는 2, 4가 리턴됩니다. 둘 다 num값과 low값이 다르기 때문에 그냥 넘어갑니다.
마지막으로 리턴되는 1은 num과 low값이 같기 때문에 1까지, 즉 {1, 4, 2} 가 한 개의 SCC에 속합니다.

뒤에서부터 하나씩 보면서 num값과 low값이 같은 정점이 나오다면, 그 정점까지가 한 SCC입니다.

구현

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
58
#include <bits/stdc++.h>
using namespace std;

int num[10101];
int low[10101];
bool visit[10101];
int cnt = 0;
vector<int> g[10101];
stack<int> s;
vector< vector<int> > ans;

void dfs(int now){
	visit[now] = 1;
	s.push(now);
	num[now] = ++cnt;
	low[now] = cnt;

	for(auto nxt : g[now]){
		if(!num[nxt]){
			dfs(nxt);
			low[now] = min(low[now], low[nxt]);
		}else if(visit[nxt]){
			low[now] = min(low[now], num[nxt]);
		}
	}

	if(low[now] == num[now]){
		vector<int> scc;
		while(!s.empty()){
			int poped = s.top(); s.pop();
			scc.push_back(poped);
			visit[poped] = 0;
			if(now == poped) break;
		}
		sort(scc.begin(), scc.end());
		ans.push_back(scc);
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;
	while(m--){
		int a, b; cin >> a >> b;
		g[a].push_back(b);
	}

	for(int i=1; i<=n; i++){
		if(!num[i]) dfs(i);
	}
	cout << ans.size() << "\n";

	sort(ans.begin(), ans.end());
	for(auto v : ans){
		for(auto i : v) cout << i << " ";
		cout << "-1\n";
	}
}