ISM Fire Safety Plan
All submissions for this problem are available.
ISM administration is planning to install fire exits in the Main Building. The Main Building is a collection of some interconnected galleries. The galleries are connected by corridors in such a way that from any gallery there is exactly one path to reach any other gallery without visiting any intermediate gallery.
However, in order to reduce installation cost, it has been decided that not every gallery will have a fire exit. Fire exits will be installed in such a way that if any gallery does not have a fire exit then at least one of its adjacent galleries must have one. The Administration has hired you to determine where to put the fire exits under this constraint.
However, as a first step, you are expected to determine the minimum number of fire exits required.
First line of the input will contain the no. of test cases T. The first line of each test case contains an integer N (1<=N<=1,000) indicating the number of galleries in this test case. Then follow N lines where the i-th (1<=i<=N) line is the adjacency list of the i-th gallery (Each gallery is given a unique identification number from 1 to N for convenience). The adjacency list for gallery i starts with an integer K (1<=K<=N-1) indicating the number of galleries adjacent to this gallery, followed by K integers giving the identification numbers of those galleries.
For each test case in the input file print a line containing the minimum number of fire exits required to meet the given constraint.
Input: 3 4 1 2 2 1 3 4 1 2 1 2 6 2 4 5 1 6 1 5 1 1 3 1 3 6 2 5 2 4 2 2 4 2 1 3 2 2 4 2 1 3 Output: 1 3 2
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.