DWITE Online Computer Programming Contest, November 2009, Problem 4
In a graph, each node has a "level" – a distance to the root (start) node. One of the special properties that could be extracted, is that if there is a connection between two nodes of the same level, then there is also a cycle of odd length in the graph, which in turn gives us more properties about the structure.
The input will contain 5 test cases: A single positive integer
The output will contain 5 lines, integer count of how many pairs of nodes have a connection, such that the shortest path from 1 to each node is equal.
Sample Input
Copy
3
1 2
3 2
1 3
10
1 2
1 3
2 3
2 4
3 5
3 6
4 5
5 6
4 7
5 7
Sample Output
Copy
1
3
Problem Resource: DWITE
Comments
Question: For the sample input, should not 4 and 6 also be a pair(2 edges from the root)?
Does anyone know?
They have to be directly connected (share an edge between them) as well as being on the same level.
It should be clarified that in the sample input and output only 2 sets of the 5 are shown
Got it