강한 연결 요소(SCC, Strongly connected components) - 코사라주와 타잔 알고리즘

* 강한 연결 요소(SCC, Strongly connected components) - 코사라주(kosaraju)와 타잔(tajan) 알고리즘

  이전에 SCC에 포스팅한 적이 있어요. 그 때는 코사라주 알고리즘에 대해서 공부한 적이 없었는데 이번에 CLRS 공부하면서 알게 됐습니다. 또 이 코사라주로부터 타잔 알고리즘을 더 쉽게 이해할 수 있게 되서 제가 이해한 방식으로 포스팅하려고 따로 글 올려봅니다.

먼저 코사라주 알고리즘부터 보겠습니다.

* 코사라주 알고리즘

- 알고리즘 순서

  1. DFS 한 번 돌며 모든 자식을 다 돌았음을 알리는 종료 시점 f[]를 저장한다.

  2. G=(V, E)에 대해 transpose of G = G^T = {(v, u) | (u, v) in G}를 정의한다.

  3. G^T에 대해 "종료 시점을 내림차순"으로 DFS를 돌린다. 각 DFS마다 해당 정점을 최초로 방문하는 모든 정점은 같은 SCC에 속한다.

  전제 1) G와 G^T는 같은 SCC를 가진다. u와 v가 G에서 서로 경로가 존재하면 G^T에서도 u와 v 역시 서로 경로가 존재한다.

  전제 2) G에서 속하는 서로 다른 SCC인 C와 C`에 대해 u in C, u` in C`이고 u에서 u`로 가는 경로가 존재한다면 v in C, v` in C`인 임의의 v와 v`에 대해 v`에서 v로 가는 경로는 존재하지 않는다.

  전제 2 증명) v`에서 v로 가는 경로가 존재한다고 가정해보자. 그러면 u에서 u`로 가는 경로가 있으므로, u`->v` 그리고 v`->v 마지막으로 v->u로 경로가 존재하기 때문에 u와 u`는 서로 경로가 존재한다. 이는 서로 다른 SCC인 C와 C`에 있다는 전제와 모순되므로 v`에서 v로 가는 경로는 존재하지 않는다.

  전제 3) 서로 다른 SCC인 C와 C`에 대해 u in C, u` in C`이고 u에서 u`로 가는 경로가 존재하면 종료시점 f에 대해 f[C] > f[C`]이다.

  전제 3 증명) u에 온 시점에서 u`를 방문해야만 하고 C`를 포함한 이후의 정점을 모두 방문해야 자식에 대한 DFS가 종료되기 때문에 필연적으로 f[C] > f[C`]이다.

  전제 4) G=(V, E)에서 서로 다른 SCC인 C와 C`에 대해 u in C, u` in C`에서 u에서 u`로 가는 경로가 존재하는 간선 집합를 Ex={(u, u`) | u in C, u` in C`, (u, u`) in E}라 하면, 이 때 G^T에서 임의의 시작정점 v` in C`에 대해 임의의 종료정점 v in C 으로 가기 위해서는 Ex 집합에 있는 간선을 이용해야만 한다. 따라서 f[] 내림차순으로 방문하는 위상을 이용하여 SCC를 구할 수 있다.

  전제 4 증명) 코사라주의 핵심이라고 볼 수 있다. 간단하게 생각해보면 C에서 C`로 갈 수 있는 간선이 있다면 C`에서 C로 가는 간선은 G^T에서 존재하게 된다. 서로 다른 SCC인 C와 C`가 G 또는 G^T에서 서로 왕복할 수 없으므로 반드시 위상값이 다르다. 따라서 이는 위상 정렬을 통해 가장 마지막 위상에 있는 것부터 가장 상위에 있는 위상까지 차례로 위상 정렬하면 SCC를 구할 수 있다.

* 코사라주의 구현 중간 - 종료 시점 f에 대해서 내림 차순 정렬

  이제 처음 DFS로 구한 종료 시점을 뜻하는 f에 대해 내림차순으로 G^T 그래프에 대해 DFS를 진행하는 것을 아실겁니다. 실제 구현하려고 하면 종료 시점을 내림차순으로 하는 것이 까다롭다는 것을 느낄 수 있습니다. 방향 그래프 G=(V, E)가 아래 그림처럼 되어 있다고 합시다.

[그림 - 방향 그래프 G]

  일단 종료시점에 대해 f[x]가 언제 종료될 지 알기 힘듭니다. 알기 위해선 트리 다이나믹을 사용한다 하더라도 이미 방문된 자식이 최대 값이 아닐 수도 있습니다. 노드 번호를 오름차순으로 DFS를 진행한다면 바로 정점 4의 경우와 같게 됩니다. 따라서 종료 시점을 제대로 얻기 위해서는 다시 순회해야 합니다. 하지만 또 순회하기에는 시간과 메모리가 필요할 수 밖에 없고, 특히 문제를 풀 때 다시 순회하지 못하는 경우가 많습니다.

  뭔가 좀 더 해보면 될 것 같은데,, 라는 느낌을 지울 수 없다면 하나 더 예시를 들어보죠. 그러면 u->v 간선이 있고 정점 v에 대한 f값을 이미 끝냈다고 가정해봅시다. 그러면 u는 당연히 v보다 큽니다. 그러면 f[u] == f[v] + 1일까요? 당연히 그렇지 않습니다. 반례는 쉽게 찾을 수 있어요. 방향 간선 집합 E = {(y, x), (x, v), (u, v), (v, z), (z, x)}라고 한다면 y에 대한 DFS를 먼저하면 f[y] = 4, f[x] = 3, f[v] = 2, f[z] = 1입니다. f[v] + 1 = 3가 되므로 f[u]를 3으로 설정하는 오류를 범할 수 있습니다. 이 예제에서는 x, v, z가 SCC를 이루니 f[u]=4가 되어야 합니다. 그렇다고 자식을 재차 방문하기엔 시간과 메모리가 아깝죠.

그래서 실제 구현할 때는 종료 시점을 배열이 아닌 스택으로 구현합니다.

- 코사라주 알고리즘 구현 예시

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
const int MAX_N = 1e4;
vector<int> E[MAX_N], E_transpose[MAX_N], C;
vector<vector<int>> scc;
stack<int> f;
int done[MAX_N];
void dfs1_2(int u) {
	done[u] = 1;
	for (int& v : E[u]) if (!done[v])
		dfs1_2(v);
	f.push(u);
}
void dfs2(int v) {
	C.push_back(v);
	done[v] = 1;
	for (int& u : E_transpose[v]) if (!done[u])
		dfs2(u);
}
int main() {
	int N, M, u, v, i;
	scanf("%d%d", &N, &M);
	while (M--) {
		scanf("%d%d", &u, &v);
		u--, v--;
		E[u].push_back(v);
		E_transpose[v].push_back(u); // v -> u
	}
	for (i = 0; i < N; i++) if (!done[i])
		dfs1_2(i);
	memset(done, 0, sizeof done);
	while (!f.empty()) {
		u = f.top(); f.pop();
		if (!done[u]) {
			C.clear();
			dfs2(u);
			sort(C.begin(), C.end());
			scc.push_back(C);
		}
	}
	printf("%d\n", scc.size());
	sort(scc.begin(), scc.end(), [](const vector<int>& a, const vector<int>& b) {
		return a[0] < b[0];
	});
	for (vector<int> scc_i : scc) {
		for (int& v : scc_i) printf("%d ", v + 1);
		puts("-1");
	}
	return 0;
}

* 타잔 알고리즘으로 이어가보기

  코사라주에서는 첫 번째 DFS에서 반환되는 값은 끝나는 시점을 스택으로 구현합니다. 위 알고리즘 순서로 보시면 아시겠지만 "DFS -> 방문 순서 재조정 -> DFS"순으로 다소 복잡한 구조를 가지고 있습니다. 단 한 번의 DFS로 SCC를 찾는 방법은 없을까요 ?

  거꾸로 생각해봅시다. 반환되는 값을 자식 값(종료 시점)이 아니라고 해봅시다. 자식 값이 아니라면? 

  바로 자기 자신 또는 부모 값을 반환하는 겁니다.

  부모의 값을 저장해야하니, 이번엔 종료 순서가 아닌 방문 순서(d 배열, discovered)를 기록합니다. 만약 u가 먼저 방문이 되었고 그 이후에 방문한 v와 같은 SCC에 있다고 해봅시다. 그러면 d[u]의 값은 d[v]에 비해 작은 값을 가지고 있고, u가 v로부터 얻은 값은 d[u]와 같거나 작을 겁니다(역방향 간선). 교차 간선에 유의하며 SCC를 구성하면 코사라주에서 원하는 SCC를 똑같이 얻을 수 있습니다.

  코사라주에서 스택은 두 번째 DFS에서의 방문 순서를 의미한다면, 타잔에서의 스택은 같은 SCC에 있을 수 있는 후보를 저장합니다. 이는 곧 종료 시점을 특정 조건에 따라 바로 구하여 결과를 도출해냅니다.

  따라서 종료 시점이 아닌 방문 시점으로 변경할 때 동치 관계(결과적으로 같은 SCC를 도출해내기 위함)를 형성하고, 스택의 용도를 바꿈으로써 타잔 알고리즘을 더 깊게 알 수 있습니다.

※ 추가적으로 타잔 알고리즘을 알고싶으신 분은 다른 글을 참고하시거나 제가 올렸던 포스팅(https://coloredrabbit.tistory.com/44)을 참고해주세요.