8061 : 강한 연결 요소
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
주어진 유향 그래프 $G = (V, E)$에서 모든 강한 연결 요소(SCC, Strongly Connected Component)들을 찾아 출력하는 프로그램을 작성하십시오.
강한 연결 요소란 그래프 내의 정점들의 부분집합 $V'$로, $V'$에 속하는 임의의 두 정점 $u, v$ 사이에 서로 도달 가능한 경로가 존재하는 최대 부분집합을 말합니다.
[제약 조건]
• $1 \le N \le 5{,}000$
• $1 \le M \le 15{,}000$
• $1 \le u, v \le N$
강한 연결 요소란 그래프 내의 정점들의 부분집합 $V'$로, $V'$에 속하는 임의의 두 정점 $u, v$ 사이에 서로 도달 가능한 경로가 존재하는 최대 부분집합을 말합니다.
[제약 조건]
• $1 \le N \le 5{,}000$
• $1 \le M \le 15{,}000$
• $1 \le u, v \le N$
입력 설명
첫째 줄에 정점의 개수 $N$과 간선의 개수 $M$이 공백으로 구분되어 주어집니다. ($1 \le N \le 5{,}000$, $1 \le M \le 15{,}000$)
둘째 줄부터 $M$개의 줄에 걸쳐 간선의 시작 정점 $u$와 끝 정점 $v$가 공백으로 구분되어 주어집니다. ($1 \le u, v \le N$)
둘째 줄부터 $M$개의 줄에 걸쳐 간선의 시작 정점 $u$와 끝 정점 $v$가 공백으로 구분되어 주어집니다. ($1 \le u, v \le N$)
출력 설명
첫째 줄에 강한 연결 요소(SCC)의 개수 $K$를 출력합니다.
다음 $K$개의 줄에는 각 SCC에 속한 정점 번호들을 오름차순으로 정렬하여 출력하고, 줄의 끝에는
이때 각 SCC는 속한 정점 중 가장 작은 번호(최솟값)를 기준으로 오름차순 정렬하여 출력해야 합니다.
다음 $K$개의 줄에는 각 SCC에 속한 정점 번호들을 오름차순으로 정렬하여 출력하고, 줄의 끝에는
-1을 출력합니다.이때 각 SCC는 속한 정점 중 가장 작은 번호(최솟값)를 기준으로 오름차순 정렬하여 출력해야 합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 6
1 2
2 3
3 1
3 4
4 5
5 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2
1 2 3 -1
4 5 -1도움
타잔(Tarjan) 알고리즘이나 코사라주(Kosaraju) 알고리즘을 사용하면 $O(V + E)$의 시간 복잡도 내에 모든 SCC를 분류할 수 있습니다.