문제 48
강한 연결 요소
$1$번부터 $N$번까지 번호가 붙은 정점과 $M$개의 방향 간선으로 이루어진 그래프가 있다.
서로 오갈 수 있는 정점들을 같은 그룹으로 묶어 출력하라.
입력
첫 번째 줄에 두 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 10\,000; 0 \le M \le 100\,000)$
두 번째 줄부터 $M$개의 줄에 걸쳐 각 방향 간선의 시작 정점과 도착 정점의 번호를 의미하는 두 정수 $u$, $v$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N; u \neq v)$
같은 방향 간선은 두 번 이상 주어지지 않는다.
출력
첫 번째 줄에 그룹의 개수를 출력한다.
두 번째 줄부터 각 줄에 한 그룹에 포함된 정점 번호를 오름차순으로 공백으로 구분해 출력하고, 마지막에 -1을 출력한다.
그룹의 출력 순서는 자유롭다. 가능한 정답이 여러 개라면 그중 아무거나 출력한다.
예제 입력 1
8 10 1 2 2 3 3 1 3 4 4 5 5 4 5 6 6 7 7 6 7 8
예제 출력 1
4 8 -1 6 7 -1 4 5 -1 1 2 3 -1
예제 입력 2
5 0
예제 출력 2
5 1 -1 2 -1 3 -1 4 -1 5 -1
공식 해설
탐색 종료 순서와 역방향 그래프 이용하기
서로 오갈 수 있는 정점들을 최대한 묶은 그룹이 강한 연결 요소(SCC)이다. 코사라주 알고리즘은 DFS 두 번으로 이를 구한다.
먼저 원래 그래프의 모든 정점을 DFS한다. 정점의 이웃 탐색을 모두 마치고 돌아올 때 그 정점을 목록에 추가한다. 아직 방문하지 않은 정점에서도 새 탐색을 시작하여 모든 정점의 종료 순서를 얻는다.
그다음 모든 간선을 뒤집은 그래프에서, 종료 순서의 역순으로 아직 방문하지 않은 정점을 골라 DFS한다. 이 DFS 한 번이 방문하는 정점들을 하나의 SCC로 묶는다.
원래 그래프에서 서로 다른 SCC 사이에 $C\to D$ 간선이 있으면 $C$의 가장 늦은 종료 시각이 $D$보다 늦다. 따라서 두 번째 탐색의 시작 SCC에는 역방향 그래프에서 아직 처리하지 않은 다른 SCC로 나가는 길이 없다. 같은 SCC 안에서는 간선을 모두 뒤집어도 서로 오갈 수 있으므로 정확히 그 SCC만 방문한다.
그룹 내부를 정렬 없이 출력하기
각 정점의 SCC 번호를 얻은 뒤 정점 번호를 $1$부터 $N$까지 순회하여 해당 그룹의 출력 배열에 넣는다. 그러면 각 그룹의 정점들이 자동으로 오름차순이 된다. 그룹의 출력 순서는 자유로우므로 따로 정렬할 필요가 없다.
그룹 수를 먼저 출력하고, 각 그룹의 정점들 뒤에 $-1$을 붙인다. 시간복잡도와 공간복잡도는 $O(N+M)$이다.
구현 · 언어별 풀이
C++ 구현
원래 그래프와 역방향 그래프를 각각 vector<vector<int>>에 저장한다. 첫 DFS의 목록에는 진입할 때가 아니라 모든 이웃을 처리한 뒤 정점을 넣는다. 두 번째 DFS 전에 방문 표시를 초기화하고 목록을 역순으로 읽는다. 깊은 경로에서는 명시적 스택으로 종료 시점을 관리할 수 있다.
C 구현
원래 그래프와 역그래프를 함께 저장한다. 첫 DFS는 정점과 다음 간선 위치의 프레임으로 종료 순서를 기록하고, 역그래프 DFS는 단순 스택으로 성분을 붙인다. 진입 순서와 종료 순서를 혼동하지 않는다.
Python 구현
첫 DFS의 종료 순서는 (정점,다음 이웃 위치) 스택으로 만든다. 역그래프를 그 순서의 역순으로 탐색해 성분을 부여한다. 정점 번호를 오름차순으로 모으면 각 성분의 출력 정렬도 쉽게 처리한다.
Java 구현
두 그래프의 인접 배열과 boolean[] 방문을 사용한다. 첫 DFS 종료 시에만 순서 배열에 넣는다. 재귀 대신 프레임 스택을 사용하고 역그래프에서는 반복 탐색으로 성분을 모은다.
Rust 구현
첫 탐색에는 (정점,다음 위치) 프레임 Vec을 사용한다. 역그래프 DFS로 성분 번호를 정한 뒤 번호별로 정점을 모은다. 미배정 성분 표식과 실제 성분 인덱스를 구분한다.
JavaScript 구현
첫 DFS는 (정점, 다음 이웃 위치)를 명시적 스택으로 저장한다. 스택에 넣을 때가 아니라 모든 이웃을 처리해 꺼낼 때 종료 순서에 추가한다. 두 번째 DFS는 그 순서의 역순으로 역그래프를 탐색하여 성분 번호를 부여한다.
Int32Array 성분 번호와 Uint8Array 방문 표시면 충분하다. 마지막에 정점 번호를 $1$부터 $N$까지 순회하여 해당 성분 배열에 추가하면 각 성분 내부가 자동으로 오름차순이 된다. 최대 깊이 $N$의 재귀나 각 그룹의 불필요한 정렬을 피한다.