응축 그래프의 최장 경로
플래티넘 V의견: 0
정점 \(N\)개와 간선 \(M\)개로 이루어진 방향 그래프가 주어진다. 이 그래프를 SCC로 압축한 응축 그래프(condensation DAG) 에서 가장 긴 경로가 지나는 SCC(정점)의 개수를 구하여라.
응축 그래프는 항상 사이클이 없는 방향 그래프(DAG)이므로, 위상 정렬 순서에 따른 동적 계획법으로 최장 경로(지나는 정점 수)를 구할 수 있다. 한 SCC만 지나는 경로의 길이는 1로 센다.
정점·간선이 많으므로 반복적 SCC 알고리즘과 반복적/위상정렬 기반 DP로 \(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 \to v\) 가 주어진다.
응축 그래프에서 최장 경로가 지나는 SCC의 개수를 출력한다.
5 5
1 2
2 3
3 1
3 4
4 5
3SCC는 \(\{1,2,3\}\to\{4\}\to\{5\}\) 의 응축 사슬을 이룬다. 최장 경로는 이 3개의 SCC를 모두 지나므로 답은 3.
3 3
1 2
2 3
3 1
1전체가 하나의 SCC이므로 응축 그래프는 정점 1개이다. 최장 경로는 1.
riseoj 작성
출처 Original
평가 및 의견
응축 그래프의 최장 경로
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
응축 그래프의 최장 경로