[그래프] SCC - Kosaraju

작성일 | In

SCC를 구하는 알고리즘 중 Kosaraju’s Algorithm을 알아봅시다.

작동 방식


이 그래프에서 SCC를 구해보겠습니다.

먼저, dfs tree를 만들어주면서, finish time을 저장해줍니다.

그 후, 그래프 상의 모든 간선을 뒤집어줍니다. (역방향 그래프)

역방향 그래프에서 finish time이 큰 정점부터 dfs를 수행해줍니다. 이 때 생성되는 dfs tree들이 각각 하나의 SCC가 됩니다.

구현 방법

BOJ2150번 문제 “Strongly Connected Component” 를 코드로 구현해봅시다.

그래프를 입력 받을 때, 역방향 그래프까지 같이 만들어줍시다.

1
2
3
int a, b; cin >> a >> b;
g[a].push_back(b);
gp[b].push_back(a);

dfs tree를 그려주면서, order라는 배열에 탐색이 먼저 끝나는 정점 순으로 저장해줍시다. (finish time)
dfs tree는 방문하지 않은 정점에 대해 dfs함수를 호출해주면서 그릴 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
void dfs(int now){
	if(visit[now]) return;
	visit[now] = 1;
	for(auto nxt : g[now]) dfs(nxt);
	order.push_back(now);
}


for(int i=1; i<=n; i++){
  if(!visit[i]) dfs(i);
}

order배열을 뒤집은 후, SCC를 구하기 위해 dfs를 다시 돌려줍니다.
이번에 dfs를 돌릴 때에는, 각 정점이 어떤 SCC에 속하는지 기록해줍니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs_rev(int now, int num){
	if(visit[now]) return;
	visit[now] = 1;
	SCC[now] = num;
	for(auto nxt : gp[now]) dfs_rev(nxt, num);
}

memset(visit, 0, sizeof(visit));
reverse(order.begin(), order.end());
int num = 0;
for(auto i : order){
  if(!SCC[i]) dfs_rev(i, ++num);
}

전체 코드

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

vector<int> g[10101]; //그래프
vector<int> gp[10101]; //역방향 그래프
bool visit[10101];
vector<int> order; //finish time 순
int n, m;
int SCC[10101];

typedef vector< vector<int> > vii;

void dfs(int now){
	if(visit[now]) return;
	visit[now] = 1;
	for(auto nxt : g[now]) dfs(nxt);
	order.push_back(now);
}

void dfs_rev(int now, int num){
	if(visit[now]) return;
	visit[now] = 1;
	SCC[now] = num;
	for(auto nxt : gp[now]) dfs_rev(nxt, num);
}

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

	for(int i=1; i<=n; i++){
		if(!visit[i]) dfs(i);
	}

	memset(visit, 0, sizeof(visit));
	reverse(order.begin(), order.end());
	int num = 0;
	for(auto i : order){
		if(!SCC[i]) dfs_rev(i, ++num);
	}
	cout << num << "\n";

	vii ans(num);
	for(int i=1; i<=n; i++){
		ans[SCC[i]-1].push_back(i);
	}
	for(int i=0; i<num; i++) sort(ans[i].begin(), ans[i].end());
	sort(ans.begin(), ans.end());

	for(auto v : ans){
		for(auto i : v) cout << i << " ";
		cout << "-1\n";
	}
}