오늘은 강 연결 성분(Strongly Connected Component)에 대해서 알아보겠습니다. 강 연결 성분(Strongly Connected Component) 강 연결 성분은 방향 그래프에서 연결 성분 내의 임의의 두 정점 u와 v에 대해 u에서 v로 가는 경로가 있고 동시에 v에서 u로 돌아오는 경로가 있는 연결 성분을 의미합니다. 강 연결 성분은 scc라고도 불리며, 이중 연결 성분과 다르게 cut point나 bridge를 포함하지 않습니다. 이러한 그래프가 있다고 해봅시다. 만약 우리가 강 연결 성분을 찾는 알고리즘을 수행한다면 아래와 같은 강 연결 성분을 찾을 수 있습니다. 강 연결 성분 알고리즘 scc를 찾기 위한 알고리즘은 대표적으로 2가지가 있습니다. 스택을 사용하는 Tarjan ..
