강한 연결 요소 (SCC, Strongly connected components)

 * 강한 연결 요소 (SCC, Strongly connected components)

  방향 그래프 상에서 두 정점 u와 v에 대해 양 방향으로 가는 경로가 모두 있을 때 두 정점은 같은 SCC에 있다고 말한다.

if vertex u has paths to vertex v and also v has paths to u, either u and v are involved in same SCC.

  이 SCC 집합은 하나의 component 내에 여러개가 생길 수 있다. 아래 그림을 보면 하나의 component에 대해 3개의 SCC가 있음을 직관적으로 알 수 있다.

  SCC의 특성 중 하나는 SSC 간의 방향 그래프를 그려보면 DAG가 나온다는 것이다.

  이는 연역적으로 정리가 가능하다.

  1. 현재 구성할 수 있는 SCC를 모두 구성했고, 하나의 component에 대해 A,B 두 개의 SCC가 있다고 가정.

  2. 만약 A에서 B로 갈 수 있는 경로가 존재하며, B에서 A로 갈 수 있는 경로가 존재한다면, A와 B가 같은 SCC에 속한다.

  3. 하지만 이는 1.에서 구성할 수 있는 모든 SCC를 구성했다고 가정했기 때문에, 2.은 거짓이 된다.

  4. 따라서 A와 B에서 경로가 존재하던지 아니면 B에서 A로 가는 경로가 존재하던지 둘 중 하나뿐이다. (같은 component에 있기 때문)

  이렇게 SCC의 DAG를 구성하는 것을 그래프 압축(condensation)이라고 한다.

  또한 SCC는 cycle과 밀접한 관련이 있으며, 하나의 component가 여러 개의 SCC로 나뉜다면 어느 한 정점에서 다른 정점으로 갈 수 없음을 알 수 있다.

* 구현

1. Tarjan algorithm

  Tarjan algorithm의 특징은 한 번의 DFS로 SCC를 구성할 수 있다는 점이다.

  단절점 알고리즘을 바탕으로 하며, 그렇기에 방문하는 것을 거꾸로 하면 순서대로 방문해야할 정점 리스트를 얻을 순 있다.

  

  먼저 DFS로 DFS spanning tree를 구성한다. 모든 정점을 단 한번만 방문한다는 것이 핵심이다.

  만약 어떤 SCC를 처음 방문 한다고 가정해보자. 그 정점을 x로 두고, 한 SCC에 속한 두 정점 간에 경로는 항상 있기 때문에 DFS(x)가 종료하기 전에 정점 x의 SCC에 속한 모든 정점을 방문하게 된다. 따라서 이 SCC에 속한 정점들은 모두 x를 루트로 하는 서브 트리에 포함된다.

  이 때 spanning tree를 잘라서 SCC를 분리할 수 없는 유일한 경우는 x와 같은 SCC에 속한 y 사이에 다른 정점 z가 껴 있는 경우뿐이다. 하지만 이 경우는 z에서 y로 가능 경로가 있고, y에서 x로 가는 경로가 있기 때문에 z에서 x로 가는 경로가 있는 것이기에 z와 x는 같은 SCC에 속하므로 가정이 모순된다.

  * Spanning tree 자르기/ SCC 분리하기

  그렇다면 어떤 간선을 잘라야 SCC가 분리 되는지 생각해보자.

  서로 다른 SCC인 A와 B가 있고, A->B라면 이 간선을 제거하면 된다. 이 때 제거된 간선의 종점은 B에 속할 것이고 이는 B의 루트가 되는 걸 알 수 있다.

  정점 u가 SCC의 루트라는 말은 u의 선조와 u가 다른 SCC에 속하는 말과 동치이며, 그러기 위해선 u에서 선조로 가는 경로가 없어야 한다. u에서 선조로 가는 경로가 있다면 항상 역방향 간선이 하나 포함되어 있어야 한다. 

  (단절점 알고리즘) u를 루트로 하는 서브 트리를 DFS로 만나는 모든 역방향 간선을 이용해 닿을 수 있는 가장 상위 정점을 찾는다. 이 정점이 u의 선조이거나 그보다 높이 있다면 이 역방향 간선을 위해 u에서 선조로 갈 수 있고, u가 SCC의 루트가 아님을 증명할 수 있다. 반대로 역방향 간선이 없고, 최대 높은 정점이 u라면 u가 SCC의 루트임을 알 수 있다.

  교차 간선의 경우 조심해야 한다. 이 경우에 이미 끝난 SCC에 대해 접근한다면 조상으로 가는 줄 알고 SCC로 판단할 수도 있기 때문이다. 

  u에서 DFS를 시작했고, 왼쪽 SCC를 먼저 탐색한 뒤, v로 온 상황이다. 그러면 w에서 왼쪽으로 가는 교차 간선을 v의 선저로 가는 역방향 간선이라고 생각하고 v가 SCC 루트가 아니라고 판정해 버린다. 따라서 이 문제를 해결하기 위해 교차 간선의 도착지점이 이미 SCC에 묶였 있는지 여부를 이용하면 이 교차 간선을 통해 조상으로 올라갈 수 있는지를 판단할 수 있다.

  이는 SCC labeling이 끝났는지 또는 해당 정점에 대해 DFS가 종료되었는지로 판단할 수 있다.

- 코드

int sccCount, discCount;
int *sccId;
int *discovered;
bool *finished;
stack<int> stk;
int scc(int n) {
	int ret = discovered[n] = discCount++;
	stk.push(n);
	for (int v : adj[n]) {
		if (discovered[v] == 0) ret = min_v(ret, scc(v));
		else if (!finished[v]) ret = min_v(ret, discovered[v]);
	}

	if (ret == discovered[n]) {
		while (1) {
			int t = stk.top();
			stk.pop();
			sccId[t] = sccCount;
			finished[t] = 1;
			if (t == n) break;
		}
		sccCount++;
	}
	return ret;
}