PROBLEM STATEMENT
Bear Limak loves algorithms and tolerates data structures.
Today he learned about Boruvka's algorithm.
Boruvka's algorithm was the first polynomial-time algorithm to find the minimum spanning tree (MST).
Moreover, it was pretty efficient because it worked in O(E log V).
You can find a detailed description of this algorithm and its history at
https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm.
Below we give a short description of Boruvka's algorithm.
This description should be used when solving this problem.
The input for Boruvka's algorithm is a simple connected undirected weighted graph G.
(Here, "simple" means there are no loops and each pair of vertices is directly connected by at
most one edge.)
The edge weights are distinct positive integers from 1 to m, where m is the number of edges in the
graph.
The minimum spanning tree of G is a subgraph H of G with the following properties:
H contains the same vertices as G.
H is connected.
The sum of weights of edges in H is as small as possible.
Here is Boruvka's algorithm in pseudocode:
Initialize H to contain all vertices of G but no edges at all.
While H is not connected yet:
For each component C in H:
Find the lightest edge in G that has exactly one endpoint in C.
Mark this edge for addition.
Add all marked edges to H.
Return H.
Note that the algorithm is deterministic: the weights are all distinct, hence each edge we mark
for addition is uniquely determined.
You are given ints n, m, and k.
Your task is to construct one arbitrary graph G with the following properties:
G is a valid input for Boruvka's algorithm, as defined above.
G has exactly n vertices and m edges. The vertices are numbered 1 through n. The edge weights are
1 through m.
Boruvka's algorithm will find the MST of G in exactly k rounds. (A round is a single iteration of
the while-cycle in the pseudocode above.)
If no such G exists, return the vector {-1}.
(That is, a vector with a single element that is minus one.)
Otherwise, return a vector with the description of your chosen G.
This vector should have 2*m elements: two for each edge.
Let answer[] denote the returned vector .
For each w between 1 and m, inclusive, take the edge with weight w and store its endpoints into
answer[2*w-2] and answer[2*w-1].
DEFINITION
Class:BearSpans
Method:findAnyGraph
Parameters:int, int, int
Returns:vector
Method signature:vector findAnyGraph(int n, int m, int k)
NOTES
-n will be between 2 and 1000, inclusive.
-m will be between n-1 and 1000, inclusive.
-m will be not greater than n*(n-1)/2.
-k will be between 1 and 1000, inclusive.
EXAMPLES
0)
17
22
1
Returns: {1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11, 1, 12, 1, 13, 1, 14, 1,
15, 1, 16, 1, 17, 2, 3, 2, 8, 3, 9, 8, 9, 10, 12, 12, 14 }
We were asked to find a graph with 17 vertices and 22 edges that will be fully solved in one round
of Boruvka's algorithm.
We can easily verify that the graph given in the example output does have the property.
The minimum spanning tree of this graph consists of the edges 1-x for all x between 2 and 17,
inclusive.
For each x, the edge 1-x is marked for addition in the first round: as the cheapest edge that
leaves vertex x.
1)
9
12
3
Returns: {6, 5, 7, 6, 1, 2, 3, 4, 8, 9, 3, 5, 7, 4, 1, 9, 6, 2, 6, 1, 1, 8, 4, 5 }
Let's take a loot at the graph given in the example output.
After the first round we have four components: {1,2}, {3,4}, {5,6,7}, {8,9}.
After the second round we have two components: {1,2,8,9} and {3,4,5,6,7}.
The third round connects the two remaining componenets so we get 3 rounds in total.
2)
9
12
7
Returns: {-1 }
3)
1000
999
970
Returns: {-1 }
4)
2
1
1
Returns: {1, 2 }
5)
3
2
1
Returns: {1, 2, 1, 3 }
6)
3
3
2
Returns: {-1 }
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.