381. How Much Can You Reach
Core1000 ms256 MBSolved by 0%
The edges are directed. Print how many vertices can be reached from vertex 1, counting vertex 1 itself.
The traversal is the one from problem 362, unchanged. What changes is that following an edge is now one-way, so reachability stops being symmetric: 1 may reach 5 while 5 cannot reach 1.
A consequence worth noticing in the tests: two vertices in the same undirected component can be unreachable from each other once the arrows are put back.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - There are no self-loops and no repeated edges.
Input
The first line contains two integers n and m, the number of vertices and
directed edges. Each of the next m lines contains two integers u and v,
a directed edge from u to v and NOT from v to u. Vertices are numbered
1 to n.
Output
Print one integer, the number of vertices reachable from vertex 1.
Input4 3
1 2
2 3
3 4
Output4
Noteis a chain leading away from vertex 1, so everything is reachable
Input2 1
2 1
Output1
Notepoints the only edge towards vertex 1, so nothing can be reached from it
Input6 5
1 2
2 3
4 5
5 6
6 4
Output3
Notehas a second group that vertex 1 never reaches
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution