[그래프 알고리즘]Tarjan 알고리즘(SCC)

Strongly Connected Component

SCC는 강한연결요소라고 합니다.

SCC는 방향그래프에서의 노드들의 부분집합으로, 한 SCC에 속하는 노드들끼리는 사이클이 존재합니다.

한 SCC에 속하는 임의의 두 노드 u, v에 대해 u에서 v로의 경로와, v에서 u로의 경로가 존재합니다.

모든 노드는 최소한 자기자신이 SCC에 속합니다.

한 방향 그래프에 존재하는 SCC들을 찾아내는 알고리즘 중에 Tarjan 알고리즘이 있습니다.

핵심 아이디어

tarjan의 알고리즘은 그래프를 DFS로 탐색하면서 방문한 순서를 기록합니다.

그리고 자신 이후의 노드에서 만난 노드중 이미 방문한 노드들이 있다면, 가장 이른 노드의 번호를 계산합니다.

이때, 가장 이른 노드의 번호가 자기 자신이라면, 자기 자신 이후로 이어지는 엣지로는 자기 이전으로 갈 수 없음을 의미하므로,

자기 자신 이후로 방문한 노드들을 하나의 SCC로 묶습니다.

구현

한 노드 이후에 방문한 노드들을 기록하기 위해 stack을 이용합니다.

이미 방문했고 SCC에 속한 노드는 무시합니다.