관문 도시
다이아몬드 V의견: 0
\(N\)개의 도시와 \(M\)개의 단방향 도로로 이루어진 도로망이 있다. 모든 물자는 수도 \(S\)에서 출발한다.
도시 \(v\)가 봉쇄되면 \(v\)를 지나는 모든 경로가 끊긴다. 어떤 도시 \(v\)를 봉쇄했을 때, 수도 \(S\)에서 더 이상 도달할 수 없게 되는 도시의 수(봉쇄된 \(v\) 자신도 원래 도달 가능했다면 포함)를 \(v\)마다 구하여라.
단, 수도 \(S\)에서 원래부터 도달할 수 없는 도시 \(v\)에 대해서는 \(-1\)을 출력한다. (\(v = S\)인 경우, \(S\)를 봉쇄하면 도달 가능했던 모든 도시를 잃으므로 그 수를 출력한다.)
각 도시를 일일이 제거해 보는 풀이는 통과할 수 없다.
\(1 \le N \le 100{,}000\)
\(1 \le M \le 300{,}000\)
\(1 \le S \le N\)
\(1 \le a, b \le N\)
첫째 줄에 도시 수 \(N\), 도로 수 \(M\), 수도 번호 \(S\)가 주어진다.
다음 \(M\)개의 줄에 단방향 도로 정보 \(a\), \(b\)가 주어진다 (도시 \(a\)에서 \(b\)로 가는 도로). 중복 간선이나 자기 자신으로의 도로가 있을 수 있다.
\(N\)개의 줄에 걸쳐, \(v = 1, 2, \dots, N\) 순서로 도시 \(v\)를 봉쇄했을 때 잃는 도시 수(도달 불가 도시는 \(-1\))를 한 줄에 하나씩 출력한다.
5 5 1
1 2
1 3
2 4
3 4
4 5
5
1
1
2
1수도 1에서 모든 도시 도달 가능. 4는 2,3 어느 쪽으로도 갈 수 있어 2나 3을 막아도 4,5는 살아있다 → 각 1. 4를 막으면 4,5를 잃어 2. 5를 막으면 5만 잃어 1. 1을 막으면 도달했던 5개 도시 모두 잃어 5.
4 2 1
1 2
2 3
3
2
1
-1도시 4는 수도 1에서 도달 불가 → \(-1\). 1을 막으면 1,2,3 모두 잃어 3. 2를 막으면 2,3을 잃어 2. 3을 막으면 3만 잃어 1.
riseoj 작성
출처 Original
평가 및 의견
관문 도시
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
관문 도시