6099 : SCC (코사라주) — 강연결요소
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
방향 그래프가 주어졌을 때, 강연결요소(SCC, Strongly Connected Component)들을 추출하는 프로그램을 코사라주(Kosaraju) 알고리즘을 활용해 작성하십시오.
강연결요소란, 구성원들 사이의 모든 두 노드에 대해 서로 왕복할 수 있는 경로가 존재하는 극대 정점 부분 집합을 뜻합니다.
출력 정렬 기준:
1. 각 SCC 내부의 원소들은 번호가 작은 것부터 오름차순으로 나열합니다.
2. 여러 SCC들 사이에서는 각 SCC의 첫 번째 원소(가장 작은 원소)를 기준으로 오름차순 정렬하여 출력합니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 1{,}000$ (정수)
• 간선 수 $M$: $0 \le M \le 5{,}000$ (정수)
• 그래프는 방향 그래프입니다.
강연결요소란, 구성원들 사이의 모든 두 노드에 대해 서로 왕복할 수 있는 경로가 존재하는 극대 정점 부분 집합을 뜻합니다.
출력 정렬 기준:
1. 각 SCC 내부의 원소들은 번호가 작은 것부터 오름차순으로 나열합니다.
2. 여러 SCC들 사이에서는 각 SCC의 첫 번째 원소(가장 작은 원소)를 기준으로 오름차순 정렬하여 출력합니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 1{,}000$ (정수)
• 간선 수 $M$: $0 \le M \le 5{,}000$ (정수)
• 그래프는 방향 그래프입니다.
입력 설명
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 1,000)과 방향 간선의 개수 M (0 ≤ M ≤ 5,000)이 주어집니다.
둘째 줄부터 M개의 줄에 방향 간선 u v가 주어집니다.
둘째 줄부터 M개의 줄에 방향 간선 u v가 주어집니다.
출력 설명
첫째 줄에 SCC의 개수 K를 출력합니다.
둘째 줄부터 K개의 줄에 걸쳐 각 SCC의 정점 번호들을 공백으로 구분하여 정렬된 순서대로 출력합니다.
둘째 줄부터 K개의 줄에 걸쳐 각 SCC의 정점 번호들을 공백으로 구분하여 정렬된 순서대로 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 5
1 2
2 3
3 1
3 4
4 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3
1 2 3
4
5
도움
코사라주 알고리즘은 1) 원래 그래프에서 DFS의 종료 순서대로 역방향 DFS의 시작점을 스택에 담고, 2) 뒤집힌 간선을 가진 역방향 그래프에서 스택 탑(Top) 원소부터 꺼내어 DFS를 다시 돌려 SCC를 탐색합니다.