Friend Circles

Difficulty: 1200 4000 ms 128 MB

graphs

N people are connected by M friendship links. Friends of friends belong to the same circle. How many circles are there (isolated people count as their own circle)?

Input: the first line has N and M; each of the next M lines has an edge u v (1-based).

Output: the number of connected components.

Constraints:

• 1 ≤ N ≤ 10⁴
• 0 ≤ M ≤ 2×10⁴
• multiple edges and self-loops may appear

Sample Tests

5 3
1 2
2 3
4 5

2

3 0

3

Read the Editorial