Minimum Water Tanks

You are given a town with \(N\) houses numbered from 1 to \(N\) and \(M\) bridges connecting some pairs of houses. Each bridge connects two houses, and all houses that are connected directly or indirectly form a connected component. In order to supply water to all houses, one water tank is needed per connected component.

Your task is to determine the minimum number of water tanks required, which is equal to the number of connected components in the graph formed by the houses and the bridges. This is a classic connectivity problem that can be solved using techniques such as depth-first search (DFS) or union-find.

inputFormat

The first line of the input contains two integers \(N\) and \(M\), where \(N\) is the number of houses and \(M\) is the number of bridges. Each of the following \(M\) lines contains two integers \(u\) and \(v\) representing a bridge between house \(u\) and house \(v\). If \(M = 0\), no additional lines follow.

outputFormat

Output a single integer—the minimum number of water tanks required (i.e. the number of connected components).

6 5
1 2
2 3
4 5
5 6
3 6

1