정점 \(N\)개와 간선 \(M\)개로 이루어진 방향 그래프가 주어진다. 모든 정점에서 도달할 수 있는 정점이 존재하는지 확인하고, 존재한다면 그러한 정점들이 이루는 집합의 크기를 출력하여라. 존재하지 않으면 \(0\) 을 출력한다.

정점 \(t\) 가 "모두에게 닿는" 정점이라는 것은, 임의의 정점 \(v\) 에서 \(t\) 로 가는 경로가 존재함을 의미한다. (이때 그러한 정점들은 모두 하나의 SCC를 이룬다.)

SCC로 압축한 응축 그래프(condensation DAG)에서 싱크(나가는 간선이 없는 SCC)가 유일하고, 모든 SCC가 그 싱크로 도달 가능할 때에만 그 싱크 SCC가 정답이며, 그 크기를 출력한다. 반복적 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\) 가 주어진다.

모든 정점에서 도달 가능한 정점들의 개수를 출력한다. 그런 정점이 없으면 0을 출력한다.

riseoj 작성

출처 Original