Problem Statement | |||||||||||||
It's the year 2051. You have some free time in June 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 you can take. There are a number of machines in a store. Each machine may depend on other machines to work properly, and you want all the machines you take to work. You noticed that although machine A may not depend directly on machine B, you may be unable to take A without B because of some indirect dependency. For example, if machine A is dependent on machine C and machine C is dependent on B, you cannot take machine A without machine B. You discovered an interesting rule while selecting your machines. If a machine A depends on machines B and C, then B is dependent on C, C is dependent on B, or both B and C depend on each other. Although the rule you found is true for direct dependencies, you were able to prove that it also holds for indirect dependencies. 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 directly dependent on. Return a int[] with all possible positive values for K in ascending order. Example: {"1 2","0 2","3",""}
The allowed K values are 1 (you take only machine 3), 2 (you take machines 2 and 3) and 4 (you take all the machines). So you should return {1,2,4}. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
| - | First machine has index 0, second has index 1 and so on. | ||||||||||||
Constraints | |||||||||||||
| - | dependencies contains between 1 and 50 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. | ||||||||||||
| - | Element i of dependencies does not contain the value i. | ||||||||||||
| - | If a machine A depends on machines B and C, then B is dependent on C, C is dependent on B, or both B and C depend on each other. | ||||||||||||
Examples | |||||||||||||
| 0) | |||||||||||||
| |||||||||||||
| 1) | |||||||||||||
| |||||||||||||
| 2) | |||||||||||||
| |||||||||||||
| 3) | |||||||||||||
| |||||||||||||