알고리즘/그래프
2020. 6. 18.
Strongly Connected Component
Strongly Connected Component (SCC)는 방향 그래프에서, 다음 조건을 만족하는 정점의 부분집합을 말합니다. 1. 부분집합에서 어떻게 두 정점 \(u,v\)를 선택하더라도 \(u\)에서 \(v\)로 가는 경로가 존재한다. 2. 부분집합에 속한 정점 \(u\)와 그렇지 않은 정점 \(v\)에 대해서, \(u\)에서 \(v\)로 가는 경로와 \(v\)에서 \(u\)로 가는 경로가 동시에 존재하지 않는다. 따라서 다음과 같은 방향 그래프는, 다음과 같이 4개의 SCC로 분할됩니다. 그래프를 이와같이 SCC로 분할하여 하나의 SCC를 하나의 정점으로 대체하면 그래프를 DAG로 나타낼 수 있게 됩니다. 일반적인 그래프를 DAG로 바꾸고 나면 위상정렬이나 DP등 다양한 작업을 할 수 있게 됩..
