PROBLEM STATEMENT
You've got your killer audio rack all hooked up, and there are wires running
every which way. Suddenly it occurs to you that you didn't double-check your
cocktail-napkin schematic to make sure there were no feedback loops. Since you
don't want to burn out your fancy components (or your ears), you need to check
for loops before turning it on. Given a list of strings representing the
connections between your components, find the shortest feedback loop in your
setup (the loop that passes through the smallest number of components), and
return the number of components that the shortest loop passes through. If there
are no loops, return -1 (and let the music begin!).
DEFINITION
Class: AudioRack
Method name: feedback
Parameters: String[]
Return type: int
Method signature: int feedback(String[] lines); (be sure your method is public)
Each String in lines represents a set of audio lines running OUT of component
N, where N is the zero-based index of the String in the list. The strings each
contain a comma-separated list of 1 to 10 integers (inclusive), formatted as
follows: (quotes and ellipsis (...) are included for clarity)
"M,M,M,M,...,M"
where each M represents the index of a node that an audio line runs to. For
example, suppose that:
lines[3] = "2,0,5,3"
This means that component 3 has lines running into components 2, 0, and 5, and
a line running into itself (3), which is definitely one of the shortest loops.
NOTES
* We will consider audio signals to only flow in one direction, that is, from
the output of each component to the inputs of other components (or the same
component).
* The audio rack is not necessarily contiguous; there may be parts that are
isolated from the rest of the system, and these may also contain loops which
must be examined.
Topcoder will ensure that:
- lines will contain 0 to 20 elements inclusive.
- each element in lines will contain a list of 1 to 10 integers inclusive,
representing components, separated by single commas as shown above, with no
leading or trailing commas.
- each element of lines will contain only the characters '0'-'9', inclusive and
','.
- no component will appear more than once in a particular element of lines.
- each component in each element of lines will refer to a valid zero-based
index in lines.
- integers will not have leading zeros, and a value of zero will be represented
by a single zero (as in "0").
EXAMPLES
lines = ["1,4","2,4","3,6","4","2,5","0","7","8","7,8"]
This represents the following set of connections:
0->1 0->4
1->2 1->4
2->3 2->6
3->4
4->2 4->5
5->0
6->7
7->8
8->7 8->8
The loops are:
0->1->2->3->4->5->0
0->4->2->3->4->5->0
0->1->4->5->0
0->4->5->0
2->3->4->2
7->8->7
8->8
Return value is 1, because the shortest loop passes only through one component
(8).
lines = ["1","2","3","4","5","0"]
Return value: 6
This is just a single 6-part loop passing through each of the 6 audio
components in the rack.
lines = ["0,1,2","0,1,2","0,1,2"]
Return value: 1
In this example, each of the 3 components is connected to every other component
(including itself). The shortest loops pass through only one component:
0->0 1->1 2->2
0->1->0 1->2->1 2->0->2
0->1->2->0 0->2->1->0
lines = ["1,2,3,4,5","0,2,3,4,5","0,1,3,4,5","0,1,2,4,5","0,1,2,3,5","0,1,2,3,4"]
Return value: 2