/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 頂点 M 辺からなる単純な有向グラフ G があり、頂点には頂点 1, 頂点 2, \ldots, 頂点 N と番号がついています。 また、i (1\leq i\leq M) 本目の辺は頂点 U_i から頂点 V_i へ張られています。
高橋君がある頂点から始めて、G の上を有向辺に沿って頂点から頂点へ移動することを繰り返します。 G の頂点のうち、高橋君がうまく経路を選ぶことで、その頂点から始めていくらでも移動を繰り返すことができるようなものの個数を求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- 0 \leq M \leq \min(N(N-1), 2\times 10^5)
- 1 \leq U_i,V_i\leq N
- U_i\neq V_i
- i\neq j ならば (U_i,V_i)\neq (U_j,V_j)
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M U_1 V_1 U_2 V_2 \vdots U_M V_M
出力
答えを出力せよ。
入力例 1
5 5 1 2 2 3 3 4 4 2 4 5
出力例 1
4
頂点 2 を始点とした場合、頂点 2 \to 頂点 3 \to 頂点 4 \to 頂点 2 \to 頂点 3 \to \cdots
と高橋君はいくらでも移動を繰り返す事ができます。
頂点 3, 頂点 4 を始点とした場合も同様です。
頂点 1 からは最初に頂点 2 に移動して、以下同様にいくらでも行動を繰り返すことができます。
一方、頂点 5 からは一度も移動することができません。
よって、条件を満たすのは頂点 1, 2, 3, 4 の 4 つであるので、 4 を出力します。
入力例 2
3 2 1 2 2 1
出力例 2
2
単純な有向グラフにおいて、2 つの頂点の間を互いに逆向きに結ぶ辺が、ともに存在する事はあり得ることに注意してください。 また、G は連結であるとは限りません。
Score : 500 points
Problem Statement
We have a simple directed graph G with N vertices and M edges. The vertices are labeled as Vertex 1, Vertex 2, \ldots, Vertex N. The i-th edge (1\leq i\leq M) goes from Vertex U_i to Vertex V_i.
Takahashi will start at a vertex and repeatedly travel on G from one vertex to another along a directed edge. How many vertices of G have the following condition: Takahashi can start at that vertex and continue traveling indefinitely by carefully choosing the path?
Constraints
- 1 \leq N \leq 2\times 10^5
- 0 \leq M \leq \min(N(N-1), 2\times 10^5)
- 1 \leq U_i,V_i\leq N
- U_i\neq V_i
- (U_i,V_i)\neq (U_j,V_j) if i\neq j.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M U_1 V_1 U_2 V_2 \vdots U_M V_M
Output
Print the answer.
Sample Input 1
5 5 1 2 2 3 3 4 4 2 4 5
Sample Output 1
4
When starting at Vertex 2, Takahashi can continue traveling indefinitely: 2 \to 3 \to 4 \to 2 \to 3 \to \cdots
The same goes when starting at Vertex 3 or Vertex 4.
From Vertex 1, he can first go to Vertex 2 and then continue traveling indefinitely again.
On the other hand, from Vertex 5, he cannot move at all.
Thus, four vertices ―Vertex 1, 2, 3, and 4― satisfy the conditions, so 4 should be printed.
Sample Input 2
3 2 1 2 2 1
Sample Output 2
2
Note that, in a simple directed graph, there may be two edges in opposite directions between the same pair of vertices. Additionally, G may not be connected.