Kosaraju's algorithm (strongly connected component)

Strongly Connected Componet, 줄여서 SCC는 단방향 그래프에서 사이클이 생겨 각 각의 지점에서 다른 각 각의 지점으로 갈 수 있을 때 하나의 집합 또는 이를 찾는 알고리즘을 통칭한다.

SCC는 단방향 그래프에서 DAG로 바꿔서 문제를 풀 때 유용하다.

SCC 중 kosarju's algorithm은 구현도 쉽고 시간 복잡도도 O(N) 이다.

1. 순서는 상관 없이 한 정점에서 시작하여 DFS로 방문하지 않은 모든 정점을 방문한다. 각 정점에서 DFS가 자신에게 돌아왔을 때 증가된 번호를 매겨 준다.

2. 모든 간선의 방향을 바꾸고 아직 방문 하지않고 매긴 번호가 큰 정점부터 rDFS(방향 바뀐 간선을 이용)를 시작하는 데 시작하는 정점에서 갈 수 있는 모든 정점들이 하나의 같은 컴포넌트 이다.

SCC 연습 문제 :Traveling Ship : http://koistudy.net/?mid=prob_page&NO=503&SEARCH=0

현금 인출기(APIO 2009) : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1683&sca=50&sfl=wr_subject&stx=%ED%98%84%EA%B8%88&sop=and