forestsize

View as PDF

Submit solution

Points: 1
Time limit: 2.0s
Memory limit: 1G

Author:
Problem type

Problem Statement

You a given a undirected forest graph (see definition below) with n nodes and m edges. Determine the number of trees in the forest graph.

NOTE: A forest graph is a graph containing multiple disconnected trees. Also think twice before starting to code.

Input Format

Your first line will contain two integers n and m. Your next m lines will contain two integers each, u and v denoting that u has an undirected edge to v. You are guaranteed these edges will form a forest graph.

Output Format

Output a single integer, the number of trees of disconnected trees in the forest graph.

Constraints

  • 1 \leq n \leq 10^5
  • 0 \leq m < n - 1
  • 0 \leq u, v < n
  • You are guaranteed there are no repeated edges.
  • You are guaranteed the edges will form a forest graph.

Sample Cases

Input 1
5 3
0 1
1 2
3 4
Output 1
2

Notice there are two trees in this forest, one is formed by the nodes \{0, 1, 2\} and the other by the nodes \{3, 4\}.

Input 2
10 6
7 0
1 4
0 1
1 2
1 3
7 8
Output 2
4

Here we can notice that a lot of the trees are single nodes, in particular nodes 5, 6 and 9 have no edges and are their own trees, all other nodes form a single tree.


Comments

There are no comments at the moment.