Count Tree Edges
EasyPractice library · +10 XPgraphstreesbfs
A tree is a connected graph with no cycles. Given a representation of a tree, count the number of edges it contains. You will be given the number of nodes and a list of edges connecting them. The graph is guaranteed to be a tree.
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 node U and node V. Nodes are numbered from 1 to N.
Output
Print a single integer: the number of edges in the tree.
Constraints
1 <= N <= 1000; M = N - 1; 1 <= U, V <= N; U != V.
Time limit 1 s (native code; slower languages get more)Memory 256 MB12 hidden tests
Example 1
Input
4 3 1 2 1 3 2 4
Output
3
A tree with 4 nodes has 3 edges. The edges are (1,2), (1,3), and (2,4).
Example 2
Input
1 0
Output
0
A tree with 1 node has 0 edges.
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
4 3 1 2 1 3 2 4
Example 2 input
1 0