강한 연결로 만들기
플래티넘 V의견: 0
정점 \(N\)개와 간선 \(M\)개로 이루어진 방향 그래프가 주어진다. 이 그래프 전체를 하나의 강한 연결 요소로 만들기 위해(즉 임의의 두 정점이 서로 도달 가능하도록) 추가해야 하는 간선의 최소 개수를 구하여라.
이미 그래프 전체가 강하게 연결되어 있다면 답은 \(0\) 이다.
먼저 SCC로 응축한 DAG를 만든다. 응축 그래프에서 들어오는 간선이 없는 SCC(소스)의 수를 \(s\), 나가는 간선이 없는 SCC(싱크)의 수를 \(t\) 라 하면, 응축 그래프가 하나의 정점이 아닐 때 정답은 \(\max(s, t)\) 이다. 반복적 SCC 알고리즘으로 \(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\) 가 주어진다.
그래프를 강하게 연결되도록 만드는 데 필요한 최소 추가 간선 수를 출력한다.
4 3
1 2
2 3
3 4
1응축 그래프는 \(1\to2\to3\to4\) 의 사슬이다. 소스 1개(정점1), 싱크 1개(정점4)이므로 \(\max(1,1)=1\). \(4\to1\) 간선 하나만 추가하면 강하게 연결된다.
3 3
1 2
2 3
3 1
0이미 하나의 SCC이므로 추가 간선이 필요 없다. 답은 0.
플래티넘 Iriseoj 작성
출처 Original
평가 및 의견
강한 연결로 만들기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
강한 연결로 만들기