2015 German Collegiate Programming Contest (GCPC)
Bounty Hunter II
Spike the bounty hunter is tracking another criminal through space. Luckily for him hyperspace travel has made the task of visiting several planets a lot easier. Each planet has a number of Astral Gates; each gate connects with a gate on another planet. These hyperspace connections are, for obvious safety reasons, one-way only with one gate being the entry point and the other gate being the exit point from hyperspace. Furthermore, the network of hyperspace connections must be loop-free to prevent the Astral Gates from exploding, a tragic lesson learned in the gate accident of 2022 that destroyed most of the moon.
While looking at his star map Spike wonders how many friends he needs to conduct a search on every planet. Each planet should not be visited by more than one friend otherwise the criminal might get suspicious and flee before he can be captured. While each person can start at a planet of their choosing and travel along the hyperspace connections from planet to planet they are still bound by the limitations of hyperspace travel.
Starts with an integer n (0 < n ≤ 1000) specifying the number of planets. The planets are numbered from 0 to n - 1. The following n lines specify the hyperspace connections. The i-th of those lines first contains the count of connections k (0 ≤ k ≤ n - 1) from planet i followed by k integers specifying the destination planets.
Output the minimum number of persons needed to visit every planet.
4 1 1 1 2 0 1 1
6 0 1 2 2 4 5 1 2 0 0