[ 알고리즘 ] SCC (Strongly Connected Compnent)

1. SCC (Strongly Connected Compnent)

방향 그래프에서 임의의 두 정점에 대해 양 방향으로 가는 경로가 모두 있을 때 두 점은 같은 SCC에 속해 있다고 한다.
즉 SCC는 모든 노드가 양방향으로 Reachable한 노드의 Maximal Subset 이다.
쉽게 말하자면 x→y가 있고 y→x가 있다면 strongly conneced하다고 한다. 사이클이 이의 가장 간단한 형태이다.

여기서 Maximal 과 Maximam의 차이를 조금 짚고 넘어갈 필요가 있응 것 같다.
Maximal 은 한국어로 번역하면 극대라고 할 수 있다. 그 상황에서 가장 큰 값으로 이해하자.
Maximam은 전체에서 가장 큰 것을 의미한다.

DFS Tree에서 여러 트리가 있을 때 하나의 트리에는 여러가지 SCC가 포함될 수 있지만,
하나의 SCC는 하나의 트리 안에서만 존재할 수 있다.
오른쪽에서 왼쪽으로 가는 Cross Edge는 존재하지만, 왼쪽에서 오른쪽으로 가는 Cross Edge가 존재하지 않기 때문이다.
SCC는 어디서 부터 시작해도 DFS Tree의 개수가 변하지 않는다.

1.1 SuperGraph

SuperNode는 SCC 안의 노드들 중 가장 큰 Post Number를 번호로 가지는 노드로, 노드 안에 SCC 그룹을 포함한다.
SuperNode들로 Supergraph를 생성해보면 Topological Sort 순서대로 SCC들이 정렬되어 있다.
이를 이용하여 SCC를 구분해볼 것이다.

1.2 SCC algorithm

SCC를 구하는데에 있어서 가장 중요한 것인 한 트리 안에 여러개 있을 수도 있는 SCC를 구별하는 것이다.
아래와같은 알고리즘을 거치면 SCC를 구별할 수 있다.

1. DFS를 돌려서 Post Num을 붙인다.
2. 모든 Edge를 반대방향으로 뒤집는다. (뒤집어도 SCC는 변하지 않음)
3. Post num이 가장 큰 노드로부터 DFS를 돌린다.
4. 그 다음 Post num이 큰 노드부터 DFS를 계속 돌린다.

이 과정을 거치면 3번에서 하나의 SCC를 찾게된다.
하나의 SCC만 찾을 수 있는 이유는 2번 때문이다.

scc

모두 반대로 돌렸기 때문에 아래에서 위로연결되는 모습을 뛴다
따라서 post num이 가장 큰것을 돌리면 post num이 작은 다른 SCC들과 연결되어있지 않다.

pre로 해도 순서가 보장되지 않고, 젤 작은 post num 으로 해도 순서가 보장되지 않는다.
두개 모두 어디서 시작하느냐, 어디를 먼저 선택하느냐의 영향을 받는다.