강한 연결 요소의 개수
플래티넘 V의견: 0
정점 \(N\)개와 간선 \(M\)개로 이루어진 방향 그래프가 주어진다. 이 그래프의 강한 연결 요소(Strongly Connected Component, SCC) 의 개수를 구하여라.
두 정점 \(u, v\) 가 같은 SCC에 속한다는 것은 \(u\) 에서 \(v\) 로, 그리고 \(v\) 에서 \(u\) 로 가는 경로가 모두 존재함을 의미한다.
정점과 간선이 매우 많으므로 재귀 깊이 문제를 피하기 위해 반복적(iterative) 타잔(Tarjan) 또는 코사라주(Kosaraju) 알고리즘으로 \(O(N+M)\) 에 해결해야 한다. 자기 루프나 중복 간선이 존재할 수 있다.
\(1 \le N \le 200{,}000\)
\(0 \le M \le 500{,}000\)
\(1 \le u, v \le N\)
첫째 줄에 정점 수 \(N\)과 간선 수 \(M\)이 주어진다.
이후 \(M\)개의 줄에 각각 간선의 두 정점 \(u\), \(v\) 가 주어지며, 이는 \(u \to v\) 방향 간선을 의미한다.
강한 연결 요소의 개수를 출력한다.
5 5
1 2
2 3
3 1
3 4
4 5
3정점 1,2,3은 서로 순환(\(1\to2\to3\to1\))하여 하나의 SCC를 이룬다. 정점 4와 5는 각각 단독 SCC이다. 따라서 SCC는 \(\{1,2,3\},\{4\},\{5\}\) 로 3개이다.
3 0
3간선이 없으므로 정점 3개가 각각 별개의 SCC이다. 답은 3.
riseoj 작성
출처 Original
평가 및 의견
강한 연결 요소의 개수
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
강한 연결 요소의 개수