Connected Components

Time limit: 0.5s
Memory limit: 64MB


You are given an undirected graph GG with NN vertices and MM edges. Find how many connected components the given graph has.

A connected component is a maximal subset of vertices from the graph such that for every two nodes AA and BB in the connected component, we can reach AA from BB using one or more edges.

Input data

The first line will contain two numbers, NN and MM, representing the number of vertices and edges the graph has. The next MM lines will contain the description of the graph, with one edge on each line.

Output data

The first line will contain a single number, representing the number of connected components the graph has.

Constraints and clarifications

  • 1N100 0001 \leq N \leq 100 \ 000
  • 1M200 0001 \leq M \leq 200 \ 000
  • 1A,BN1 \leq A, B \leq N, ABA \neq B
  • There are no two identical edges.
  • For tests worth 4040 points, N1 000N \leq 1 \ 000.

Example 1


6 3
1 2
1 4
3 5




Vertexes 11, 22 and 44 are in the same connected component.
Vertexes 33 and 55 are in the same connected component.
Vertex 66 is also in its own connected component.

Therefore, we have 33 connected components.

Example 2


4 2
1 2
3 4



Problem info

ID: 2036

Editor: stefdasca


Log in or sign up to be able to send submissions!