2015 German Collegiate Programming Contest (GCPC)

Legacy Code

Once again you lost days refactoring code, which never runs in the first place. Enough is enough - your time is better spent writing a tool that finds unused code!

Your software is divided into packages and executables. A package is a collection of methods. Executables are packages defining among other methods exactly one method with name PROGRAM. This method is executed on the start of the corresponding executable. Ordinary packages have no method named PROGRAM.

Each method is uniquely identified by the combination of package and method names. E.g. the method with the identifier SuperGame::PROGRAM would be the main method of the executable SuperGame.

For every method in your software you are given a list of methods directly invoking it. Thus you can easily identify methods, that are never called from any method. However, your task is more challenging: you have to find unused methods. These are methods that are never reached by the control flow of any executable in your software.


The first line contains an integer n (1n400), the number of methods in your software.

Each method is described by two lines, totaling in 2 * n lines. The first line consists of the unique identifier of the method and ki (0kin), the number of methods directly invoking this one. The second line consists of a set of ki identifiers of these calling methods or is empty if there are no such methods, i.e. ki = 0.

Method identifiers consist of a package name followed by two colons and a method name like Packagename::Methodname. Both strings, the package and the method name, each consist of up to 20 lowercase, uppercase characters or digits (a-z, A-Z, 0-9).

There will be exactly n different method identifiers mentioned in the input.


A line containing the number of unused methods in your software.

Time limit 1 second
Memory limit 128 MiB
Input example #1
SuperGame::PROGRAM 0

HelpPackage::HelpFunction 2
HelpPackage::HelpFunction SuperGame::PROGRAM
Output example #1
Input example #2
Loop::CallA 1
Loop::CallB 1
Output example #2
Source 2015 German Collegiate Programming Contest (GCPC), June 20, Problem H