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 N1 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 N1 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:

1N2×1051u,vN

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

?