BearSpans | Topcoder Archive

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 int[] {-1}. (That is, a int[] with a single element that is minus one.)

Otherwise, return a int[] with the description of your chosen G. This int[] should have 2*m elements: two for each edge. Let answer[] denote the returned int[]. 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:: int[]
Method signature:: int[] findAnyGraph(int n, int m, int k)
(be sure your method is public)

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.

Constraints

Examples

```
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.
```
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.
```
9
```
```
12
```
```
7
```
```
Returns: {-1 }
```
```
1000
```
```
999
```
```
970
```
```
Returns: {-1 }
```
```
2
```
```
1
```
```
1
```
```
Returns: {1, 2 }
```
```
3
```
```
2
```
```
1
```
```
Returns: {1, 2, 1, 3 }
```
```
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)2024, Topcoder, Inc. All rights reserved.