Kosaraju에서 첫 DFS의 종료 순서를 저장한 뒤 transpose를 역순으로 탐색하는 이유는 무엇인가요?

첫 DFS가 남기는 것은 발견 순서가 아니라 각 정점의 종료 순서입니다. 응축 그래프에서 서로 다른 SCC 사이에 C1→C2가 있으면 첫 pass의 component별 최대 종료 시각이 두 component의 방향을 구분하는 순서가 됩니다. 간선을 뒤집은 transpose에서는 방향이 C2→C1이 되므로, 마지막으로 끝난 정점부터 transpose DFS를 시작하면 한 SCC 안에서 수집이 닫히고 이미 처리하지 않은 다른 SCC로 새지 않습니다. 이 finish-order와 transpose의 조합이 두 번째 DFS의 경계를 만든다는 것이 이유입니다.

예를 들어 {A,B} 내부에 A↔B, {C,D} 내부에 C↔D, 그리고 B→C가 있다고 하겠습니다. 원래 응축 간선은 X→Y, transpose는 Y→X입니다. 첫 pass의 종료시각에 따라 X가 먼저 두 번째 시작점으로 선택되는 순서를 얻으면 transpose에서 X에서 나가는 외부 간선이 없어 X만 pop할 수 있습니다. 반대로 임의 discovery order를 사용하면 transpose 탐색이 이미 다른 component로 연결된 방향을 따라 경계를 넘을 수 있습니다. 실제 정점 목록은 인접 리스트 순서에 따라 달라도 분할은 같아야 합니다.

구현에서는 첫 pass의 finish 배열을 보존하고, 두 번째 pass 전에 visited만 초기화합니다. 각 두 번째 DFS가 방문한 정점에 새 component ID를 부여하며, disconnected graph라면 첫 pass도 모든 미방문 정점에서 시작합니다. Kahn 위상 정렬의 큐 순서와 finish order는 같은 자료가 아니고, transpose를 만들 때 원래 그래프의 adjacency를 덮어쓰지 않도록 두 표현을 분리하거나 역간선을 별도로 저장해야 합니다.

두 번째 pass의 각 시작점에서 모은 정점은 transpose에서 도달 가능한 집합이지만, finish 우선순위가 보장하는 방향 때문에 그 집합이 정확히 하나의 원래 SCC가 됩니다. 따라서 첫 pass의 배열을 단순히 역순으로 for 순회하거나 stack에서 pop하는 것은 괜찮지만, 그 배열을 정점 번호순으로 다시 정렬하면 안 됩니다. 테스트에서는 {A,B}와 {C,D}의 component ID가 0,1인지 1,0인지를 고정하지 말고, 각 ID 내부의 상호 도달성과 ID 사이의 단방향 간선을 검사해야 인접 리스트 순서에 독립적인 결과가 됩니다.