SPOJ.com - Problem DEPEND

DEPEND - Dependency Problems

We bought a brand new computer and now we would like to install an operating system. The only problem is that our chosen operating system consists of many packages and they cannot be installed in an arbitrary order. E.g. you cannot install the package tuxracer, which depends on the package libSDL, before you install libSDL. But libSDL can depend on another packages and so on. The packages may only be installed one at a time. You may install a package only if you already installed all packages it depends on. Your task is to determine how many packages can be installed on our computer.

Input file specification

The input file contains a single line for each available package. The line for each package P begins with the name of the package. The name of each package is a non-empty string of printable characters containing no spaces. Following the name of the package P is the dependency list of P. The dependency list is simply a list of names of packages that P depends on, separated by spaces. A whitespace followed by a single 0 (zero) is at the end of each line. You may assume that no package has the name '0'.

The dependency list of a package P may be empty; in that case, P does not depend on any packages and may be installed immediately. It is possible that a package Q occurs in the dependency list of a package P more than once; this merely means that P depends on Q, nothing more. Only the packages that have a dependency list in the input file are available and may be installed. It is possible that a package P depends on a package that is not available. Such a package cannot be installed.

The number of lines in the input file will be less than 9000.

Output file specification

The output consists of one number -- the maximum number of packages that may be installed on the computer.

Example

Input file
a b c b 0
b c 0
c 0
d e f 0
e f 0
f e 0
g h 0

Output file
3

Note

Package c can be installed immediately. Package b depends only on c, and hence can also be installed once we installed c. Finally, package a depends only on b and c and can now also be installed. It is easy to verify that no other packages can be installed.

Submit solution!

Added by:	Fudan University Problem Setters
Date:	2007-12-01
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: C99 ERL JS-RHINO
Resource:	IPSC 2003

hide comments



2015-06-03 20:08:58 Vaibhav Gosain The number of lines in the input file is NOT less than 9000. however, an upper limit 10000 works.
2015-05-06 04:49:23 LeppyR64 There is a newline at the end of the input which makes reading line by line and checking for EOF tricky.
2014-11-18 21:52:21 Sanjeev Kumar Number of input lines >9000 .
2012-05-25 06:57:24 Anshul how input file will be terminated? will it be terminated by "0"?
2012-05-22 08:32:29 Kirtika Ruchandani Test case should have been better. b appears twice on a's dependency list. And there is a circular dependency between e and f.
2012-05-16 19:27:47 Amit Rai i m getting tle...is there any efficient method to take input..i m using getline
2011-04-21 10:53:02 Parag gupta can u plz check the solution ID : 4995751 i am getting WA. Are there any worst cases ?
2010-05-06 11:20:31 Ravi Kiran For those people who have problems assuming an upper limit on the number of different type of package names,I think 10000 is a decent estimate.I got ac assuming that!