Can Reach All Nodes
MediumPractice library · +20 XPgraphsbfsdfs
Given a directed graph with N nodes and M edges, determine if it's possible to reach every node starting from node 1. If it is, print 'YES'. Otherwise, print 'NO'.
Input
The first line contains two integers N and M (1 <= N <= 200000, 0 <= M <= 200000). The next M lines each contain two integers u and v, representing a directed edge from node u to node v (1 <= u, v <= N).
Output
Print 'YES' if all nodes are reachable from node 1, and 'NO' otherwise.
Constraints
1 <= N <= 200000 0 <= M <= 200000
Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
5 4 1 2 1 3 2 4 3 5
Output
YES
All nodes 2, 3, 4, 5 are reachable from node 1.
Example 2
Input
4 3 1 2 2 3 4 1
Output
NO
Node 4 is not reachable from node 1.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 4 1 2 1 3 2 4 3 5
Example 2 input
4 3 1 2 2 3 4 1