강한 연결 요소(SCC) 계산기

방향 그래프에서 서로 오갈 수 있는 정점들의 묶음입니다. u에서 v로도, v에서 u로도 갈 수 있는 관계는 동치관계라 정점 전체가 묶음으로 깔끔히 갈립니다. 모듈 사이 순환 의존을 찾는 일이 정확히 이 계산이며, 한 묶음에 든 모듈들은 서로를 끌어안고 있어 따로 떼어 낼 수 없습니다.

그 정점에서 아직 탐색 중인(스택에 남아 있는) 정점까지 타고 갈 수 있는 가장 작은 발견 순번입니다. 자식을 다 보고 돌아왔을 때 low = index이면 그 정점이 묶음의 뿌리입니다. 자기보다 먼저 발견된 정점으로 돌아가는 길이 하나도 없다는 뜻이라, 스택에 자기 위로 쌓인 것들이 통째로 한 묶음이 됩니다.

이미 다른 묶음으로 확정된 정점을 보고 low를 낮추는 것입니다. 그러면 서로 다른 묶음이 하나로 붙어 버립니다. 「아직 스택에 남아 있는가」를 따로 표시해 두고 그 경우에만 낮춰야 하며, 이미 확정된 정점을 향하는 간선은 무시해야 합니다.

두 묶음 사이에 양방향 길이 있으면 애초에 한 묶음이었을 테니 모순이기 때문입니다. 그래서 위상 정렬이 실패하는 그래프라도 SCC로 축약하면 반드시 정렬됩니다. 빌드 순서나 모듈 계층을 정할 때 쓰는 방법이 이것입니다. 덧붙여 타잔은 묶음을 축약 그래프의 위상 역순으로 뱉으므로, 뒤집기만 하면 따로 정렬할 필요도 없습니다.

자기 자신으로 가는 간선이 있으면 크기가 1이어도 순환입니다. 그렇지 않으면 순환이 아닙니다. 순환 의존을 찾는 것이 목적이라면 이 자기 순환을 빠뜨리면 안 됩니다. 모듈이 자기를 import 하는 일은 드물지만 빌드 규칙이나 상태 기계에서는 흔합니다.

그쪽은 방향을 무시했을 때의 연결 요소입니다. A → B만 있고 되돌아오는 길이 없으면 방향을 무시하면 한 덩어리이지만, 강한 연결 요소로는 둘로 갈립니다. 순환 의존을 찾을 때 필요한 것은 방향을 지키는 이쪽입니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.