Problem Statement |
| | We have a list of airline flights (directed edges between two nodes in a graph), and want to determine how many distinct directed quadrilaterals (directed cycles of length 4, which contain 4 distinct nodes) there are in the flight graph such that the nodes on opposite corners of the quadrilateral are not connected in either direction. Thus, we would count the graph on the left, but not the one on the right (the diagonal edge can be directed either way, or both ways - it doesn't matter):
o--->o o--->o
^ ^ ^\ ^
| | | \ |
| v | \ v
o<-->o o<-->o
You will be given a String[] flights representing the flights. Element i of flights is a single space delimited list of integers (without extra leading 0's or leading/trailing spaces), where each integer j in the list indicates that there is an edge from i to j. An integer, j may appear more than once in element i meaning that there are multiple flights from i to j, each of which should be considered distinct. However, regardless of how many flights there are from one node to another, a quadrilateral must contain exactly 4 distinct nodes. Two quadrilaterals are considered distinct if and only if the sets of flights that they use are distinct. Thus, there may be many quadrilaterals that use the same four nodes, but different edges. Your task is to write a class DQuads, with a method count, which returns the total number of distinct quadrilaterals.
|
| |
Definition |
| | | Class: | DQuads | | Method: | count | | Parameters: | String[] | | Returns: | int | | Method signature: | int count(String[] flights) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | flights will contain between 4 and 50 elements, inclusive. |
| - | Each element of flights will be a single space delimited list of integers, with no extra leading 0's and no leading or trailing spaces. |
| - | Each integer in each element of flights will be between 0 and the length of flights - 1, inclusive. |
| - | Each element of flights will contain between 0 and 50 characters, inclusive. |
| - | Element i of flights will not contain the integer i as one of its terms. |
| |
Examples |
| 0) | |
| | {"1 1 1 1 1 1 1 1 1 1","2","3","0"} |
| Returns: 10 | | This is just a single directed square. Since there are 10 edges from 0 to 1, there are 10 distinct, directed quadrilaterals. |
|
|
| 1) | |
| | {"1 1 1 1 1 1 1 1 1 1","2","3","0 1"} |
| Returns: 0 | | This is the same as the last example, except with a cross edge from 3 to 1 included. The cross edge is in all the quadrilaterals from the previous example, and so none of them count any more. |
|
|
| 2) | |
| | {"","6 0 2","","6 6 4","6 5 5 0","",""} |
| Returns: 0 | |
|
| 3) | |
| | |
| 4) | |
| | {"3 4 8 3 7","0","4 0","","1 7 7 0","0 0 2","5 4 8 3 8","5 4 5 5 6",""} |
| Returns: 6 | |
|
| 5) | |
| | {"3 3 6","0","5 5 6 3","2 4 1 4","6 3 6 6","3","5 0 2"} |
| Returns: 26 | |
|
| 6) | |
| | {"8 1 2 4 8 12 4 5 11 10 6 2","5 3 15 7 15 15 12 0 8 9 2 0 13 9 8 7 4 7 9 11 11",
"6 7 11 9 10 1 12 9","6 6 9 7 6 1 14 1 6 7 10 6 15 6 14 16 10 11 13 4 7",
"14 15 16 0 13 2 5 16 6","2 7 16 13 16 10 16 0 8 6 0 2 6",
"8 8 4 11 3 14 9 14 14 0 5 10 13 3 11 9 5 7","13 15 6 1 3 13 6 6 8 9 6 4 10",
"4 0 1 4 12 1 2 0 14 9 6 4 16 10 7 6 9 7 13 14","11 12 4 12",
"6 4 4 9 3 1 8 0 14 14 9 14 16 5 8 16 5 12 4 5 1 12",
"14 7 14 8 4 16 6 3 13 6 10 7 13 3","15 4","12 14 14 0 8 12 11 4 3 1 12 1",
"13 4 4 6 12 0","9 0 2 9 5 10","6 15 6 13 4 5 1 6"} |
| Returns: 140 | |
|