TopCoder problem "GalaxyTrip" used in SRM 290 (Division II Level Three)



Problem Statement

    

It's the year 2059. You have some free time in May this year and want to visit an interesting galaxy. You will need some machines during your trip and you are wondering how many of them can you take.

There are a number of machines in a store. Each machine may need some other machines to work properly, and you want all the machines you take to work. Luckily for you, in the year 2053, a special rule was introduced to make customers' lives easier. The rule says that if a machine A depends on another machine B, then machine B also depends on machine A.

You want to buy K different machines such that all of them will work properly. You are given a String[] dependencies describing the dependencies between the machines. Element i of dependencies is a space delimited list of machines that machine i is dependent on. Return a int[] with all possible positive values for K in ascending order.





Example: 
 {"1 2", "0", "0", ""}
  • Machine 0 needs machines 1 and 2 to work
  • Machine 1 needs machine 0 to work
  • Machine 2 needs machine 0 to work
  • Machine 3 does not need any other machine to work

The allowed K values are 1 (you take only machine 3), 3 (you take machines 0,1,2) and 4 (you take all the machines). So you should return {1,3,4}.

 

Definition

    
Class:GalaxyTrip
Method:possibleValues
Parameters:String[]
Returns:int[]
Method signature:int[] possibleValues(String[] dependencies)
(be sure your method is public)
    
 

Notes

-First machine has index 0, second has index 1 and so on.
 

Constraints

-dependencies contains between 1 and 30 elements, inclusive.
-Each element of dependencies contains between 0 and 50 characters, inclusive.
-Each element of dependencies is a space delimited list of integers.
-Each integer in dependencies is between 0 and the number of elements in dependencies - 1, inclusive, and contains no extra leading zeros.
-Each element of dependencies contains no duplicate values.
-If element i of dependencies contains the value j, then element j of dependencies contains the value i.
-Element i of dependencies does not contain the value i.
 

Examples

0)
    
{"1 2", "0", "0", ""}
Returns: {1, 3, 4 }
The example from the problem statement.
1)
    
{"1 2", "0 2", "0 1"}
Returns: {3 }
We have to take all three machines.
2)
    
{"","","",""}
Returns: {1, 2, 3, 4 }
We can take any number of these machines since there are no dependencies.
3)
    
{"4 2", "3", "0 4", "1", "0 2", "6", "5"}
Returns: {2, 3, 4, 5, 7 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5980

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9811&pm=5980

Writer:

hauser

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Graph Theory