문제 분류 수업 진도 대회 채점현황 순위 질문게시판
게임
스도쿠 타이핑 리듬 타자게임 타이핑 테트리스 타이핑 인베이더 타이핑 지뢰찾기 8192 공룡게임 타이핑 플래피버드 랭킹
로그인

6099 : SCC (코사라주) — 강연결요소

•시간제한: 1.000 S •메모리제한: 256 MB •제출: 0 •통과: 0 •만든사람: suakii

6099 : SCC (코사라주) — 강연결요소

시간 1.000s · 메모리 256MB · 제출 0 · 정답 0

문제 설명

방향 그래프가 주어졌을 때, 강연결요소(SCC, Strongly Connected Component)들을 추출하는 프로그램을 코사라주(Kosaraju) 알고리즘을 활용해 작성하십시오.
강연결요소란, 구성원들 사이의 모든 두 노드에 대해 서로 왕복할 수 있는 경로가 존재하는 극대 정점 부분 집합을 뜻합니다.

출력 정렬 기준:
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가 주어집니다.

출력 설명

첫째 줄에 SCC의 개수 K를 출력합니다.
둘째 줄부터 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를 탐색합니다.

출처/분류

NOTICE  —  BFStudy OJ 정보샘
애들아, 문제 많이 풀고 게임 잠깐 하는거지?
— 정보샘