SCC는 Strongly Connected Component의 약자로, 강한 연결 요소를 의미합니다.
어떤 강한 연결 요소 안에 있는 정점은, 서로 이동이 가능합니다. 다시 말해, 같은 강한 연결 요소에 있다면, 갈 수 있음을 의미합니다. 방향 그래프에서 정의됩니다.
SCC알고리즘은 그래프를 Strongly Conneted한 서브 그래프로 나누는 알고리즘입니다.
위 그림과 같은 식으로 그래프를 몇 개의 서브 그래프로 나누는 알고리즘입니다.
SCC를 사용하면 사이클이 있는 방향 그래프를 DAG로 바꾸어서 다른 여러 알고리즘을 적용할 수 있게 해줍니다.
앞으로 두 개의 글에 걸쳐 SCC를 구하는 알고리즘을 알아보도록 하겠습니다.