Surveillance

4.7

3 votes
Algorithms, Depth First Search, Graphs, C++
Problem

A country consists of \(N \) cities. These cities are connected with each other using \(N - 1\) bidirectional roads that are in the form of a tree. Each city is numbered from \(1\) to \(N \)

You want to safeguard all the roads in the country from any danger, and therefore, you decide to place cameras in certain cities. A camera in a city can safeguard all the roads directly connected to it.

Your task is to determine the minimum number of cameras that are required to safeguard the entire country.

Input Format:

  • The first line contains an integer \(N \) denoting the number of cities in the country.
  • The next \(N - 1\) lines contain two space-separated integers \(u \) and \(v \) denoting a bidirectional road between cities \(u \) and \(v \).

Output Format:

Print a single integer that represents the minimum number of cameras required to safeguard the country. 

Constraints:

\(1 \le N \le 2 \times 10^5 \\ 1 \le u, v \le N\)

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

City 1 is connected to all the other cities in the country. If you place a camera in city 1, then all the cities and roads are safeguarded. Hence, the minimum number of cameras required is 1.

Editor Image

?