서론 SCC(Strongly Connected Components)를 구할 때는 크게 타잔 알고리즘과 코사라주 알고리즘을 사용한다. 그 중에서도 코사라주 알고리즘을 사용하는 편이다. 최근에 코사라주 알고리즘의 정당성에 대한 증명을 알게 되어서, 나의 블로그에는 알고리즘의 정당성에 관한 내용이 하나도 없는 것 같아서 글을 적어보려고 한다. 먼저 읽고 와야하는 글 - SCC와 코사라주 알고리즘 - DFS ordering (혹은 Euler Tour. 꼭 이 글 안 봐도 됨) 사전 준비 왼쪽과 같은 그래프에서 오른쪽과 같이 색깔별로 그룹을 묶었다. 이는 위의 글에서도 알 수 있듯이 코사라주 알고리즘을 통해 얻은 결과이며, 이 그룹이 SCC가 맞음을 증명할 것이다. 어떤 그룹이 SCC가 맞다는 것을 증명하기 위해..