Skip to main content

Cisco

Cisco OA-2 2022

Problem Description

Company ABC operates a corporate campus that consists of multiple buildings, which may or may not be linked to each other.

Goal: Alice in figuring out the minimum number of mail rooms required to ensure all buildings are adequately serviced, considering the following constraints:

Constraints:

  • Each building can accommodate only one mail room.
  • A building equipped with a mail room will service any directly connected buildings, meaning those connected buildings may not need their own mail room unless absolutely necessary.
  • Buildings that are isolated, without connections to others, will require their own mail rooms.

Inputs

  • The first line contains an integer P, i.e. the total number of buildings in the campus.
  • The second line contains an integer N, i.e. the number of connections. Each connection is represented as 'X Y', e.g., '10 20', which indicates a link between Building 10 and Building 20.
  • Next N lines contain the first building connected by the link, i.e. X. The other endpoint would be at the index of the current line + N. The next N lines contain the second building connected by the link, i.e. Y.

Output: The number indicates the minimum number of mail rooms needed.

Example 1:

Input:
6
5
1 2
2 3
2 5
5 4
5 6

Output:
2