Mail Rooms For Office Buildings :
Difficulty Level : Medium
Submissions : 571
Asked In :
Marks :10
: 11 | : 0
Company ABC has corporate campus with multiple buildings. These buildings may or may not be connected to one another. Those buildings which are connected form a tree-structure.
Mail rooms are to be setup in some buildings so that all the buildings are served with the following conditions:
- Every building can have atmost 1 mail room.
- A building having a mail room will serve itself and also service buildings directly connected to it. Hence those directly connected buildings may not host a mail room unless required otherwise.
- In case a building is not connected to any other building, then it will need its own mail room.
Please help Alisa determine the least number of mail rooms to be setup so that all buildings are serviced.
The first line contains an integer $$$n$$$ (1 $$$\le$$$ $$$n$$$ $$$\le$$$ $$$10^{5}$$$), the number of buildings.
The second line contains an integer $$$m$$$ (0 $$$\le$$$ $$$m$$$ $$$\le$$$ $$$n-1$$$), the number of connections.
Each of the next $$$m$$$ lines contain two integer $$$u$$$ and $$$v$$$ (1 $$$\le$$$ $$$u$$$,$$$v$$$ $$$\le$$$ $$$n$$$, $$$u$$$ $$$\ne$$$ $$$v$$$), denoting that building $$$u$$$ is directly connected to building $$$v$$$.
A single integer indicating the minimum number of mail rooms needed.
6 0
6
6 3 2 1 6 1 5 1
3
6 5 1 2 2 3 2 5 5 4 5 6
2
