SCC (1) 썸네일형 리스트형 130. Strongly Connected Component 유향 그래프에 존재하는 어떤 컴포넌트는 다음과 같은 조건을 만족할 경우 강결합 컴포넌트(Strongly Connected Component, SCC)라고 부른다. 컴포넌트에 속하는 임의의 두 정점 $u$와 $v$에 대해 $u$에서 $v$로 가는 경로와 $v$에서 $u$로 가는 경로가 모두 존재한다. 컴포넌트에 속하는 임의의 정점 $u$와 컴포넌트에 속하지 않는 임의의 정점 $v$에 대해 $u$에서 $v$로 가는 경로가 존재하지 않거나, $v$에서 $u$로 가는 경로가 존재하지 않는다. 그래프를 강결합 컴포넌트끼리 분리하면 같은 컴포넌트에 속한 정점들 사이에는 모두 경로가 존재하고, 다른 컴포넌트에 속한 정점들 사이에는 그렇지 않다. 따라서 같은 강결합 컴포넌트에 속한 정점들끼리 묶어서 새로운 그래프를 만.. 이전 1 다음
