hellogaon

SCC(Strongly Connected Component)는 강한 연결 요소이라고도 불리며유향그래프 상에서 두 정점 u와 v에 대해 양방향으로 가는 경로가 모두 있을 때 같은 SCC에 있다고 표현합니다.그래프를 SCC로 분리하는 방법으로는 타잔의 알고리즘을 사용합니다.이 알고리즘은 정점을 담는 하나의 스택과 한 번의 DFS만을 이용하여 분리하는데원리는 앞서 배운 간선 분류를 이용하여 아래와 같이 설명할 수 있습니다. u의 자손 v에 대하여 v를 루트로 하는 서브트리에서 v보다 먼저 발견된 정점으로 가는 역방향 간선이 있을 때,v보다 먼저 발견되었으면서 아직 SCC로 묶여있지 않은 정점으로 가는 교차 간선이 있다면 간선 (u, v)를 끊어서는 안된다. 이는 절단점 확인 알고리즘과 일정 부분 유사하며 추가..