Count Nodes in Component
EasyPractice library · +10 XPgraphsbfsdfs
Given an undirected graph with N nodes and M edges, find the number of nodes in the connected component that contains node 0. Nodes are numbered from 0 to N-1.
Input
The first line contains two integers N and M, the number of nodes and edges. The next M lines each contain two integers u and v, representing an edge between nodes u and v.
Output
Print a single integer: the number of nodes in the connected component containing node 0.
Constraints
1 <= N <= 1000, 0 <= M <= 1000, 0 <= u, v < N
Time limit 1 s (native code; slower languages get more)Memory 256 MB13 hidden tests
Example 1
Input
5 4 0 1 1 2 3 4 0 2
Output
3
Nodes 0, 1, 2 are connected. Nodes 3, 4 form another component. The component of node 0 has 3 nodes.
Example 2
Input
4 1 1 2
Output
1
Node 0 is isolated. Its component has only 1 node.
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 0 1 1 2 3 4 0 2
Example 2 input
4 1 1 2