Watchmen Trouble :
Difficulty Level : Hard
Submissions : 203
Asked In :
Marks :100
: 1 | : 0
A river has $$$N$$$ checkpoints on its left side and $$$M$$$ checkpoints on its right side. $$$P$$$ bridges are built connecting checkpoints across the river. Guards needs to be placed on checkpoints and a guard can protect all the bridges on which this checkpoint is present. There can be more than one guard to protect a single bridge.
Find the minimum number of guards required to protect all the bridges over the river.
The first line of input consists of 2 space separated integers $$$N$$$ and $$$M$$$ $$$-$$$ the number of checkpoints on the left and right side of the river respectively $$$(1 \leq N, M, \leq 100)$$$. The second line of input consists of a single integer $$$P$$$ $$$-$$$ the total number of bridges across the river $$$(1 \leq P \leq 100)$$$. Then the next $$$P$$$ lines, each consist of 2 space separated integers $$$u$$$, $$$v$$$ denoting that there is a bridge between $$$u_{th}$$$ checkpoint on the left side and $$$v_{th}$$$ checkpoint on the right side $$$(1 \leq u \leq N)$$$ $$$(1 \leq v \leq M)$$$.
The output should consist of a single integer $$$-$$$ the minimum number of guards required to protect all the bridges over the river.
4 3 4 1 3 1 2 2 2 4 1
3
