ainote

'강한연결요소'라고 불리는 Strongly Connected Component (SCC)에 대해 알아봅시다. 1. SCC의 정의 방향 그래프 $G=(V, E)$에서, 어느 노드들의 그룹 $X$가 있다고 했을 때, $X$에서 임의의 두 노드 $u, v$를 골랐을 때 $u$에서 $v$로 가는 경로가 존재한다라는 조건을 만족시키면 $X$를 strongly connected component라고 합니다. SCC의 정의는 maximal하게 형성된 strongly connected component입니다. maximal하다는 것이 무엇인지 아래의 예시를 통해 알아봅시다. 위와 같은 방향 그래프에서 세 노드로 구성된 초록색 그룹이 SCC입니다. 파란색 노드는 그 자체로서 SCC입니다. 그런데 두 개의 초록색 노드를 ..