A strange problem

Правка en8, от mutsuki, 2022-06-03 19:15:28

I came up with a strange problem and find it hard for me to solve it, so i write this topic to ask for help.

Consider a point grid, for example, a 2x3 point grid may looks like this:

o o o
o o o

Now we connect each pair of adjacent points.

o--o--o
|  |  |
o--o--o

As we have some points and edges, it now becomes a graph! Now we are gonna find one of its spanning tree. Like this one:

o--o--o
|  |
o  o--o

We can see that this tree is a 'rectangle'. Trees obtained by this way is called a rect-tree. Now, consider this rect-tree:

n=6
1 6
1 2
2 3
2 4
4 5

We can turn it back into a grid. Like this:

1  2  3
o--o--o
|  |
o  o--o
6  4  5

The problem is here:

Give you a rect-tree, please turn it back into a grid. Output the points in the grid from top to bottom, left to right.

Input: Integer n,m, then n*m-1 lines which describes the tree.

Output: n*m numbers.

Case 1: Input 2 3

1 6
1 2
2 3
2 4
4 5

Output:

1 2 3
6 4 5

At first, i thought this problem was a piece of cake and can be easily solved with 2 < n,m < 5000. However, now I find it hard to solve even when 2< n,m < 5. Can anyone help me?

By the way, here are some more testcases.

Input:

3 3
1 2
1 3
1 4
4 5
4 6
5 7
4 8
6 9

Output:

2 1 3
5 4 6
7 8 9

It looks like this

o--o--o
   |
o--o--o
|  |  |
o  o  o
Теги tree, problem solving

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский mutsuki 2022-06-03 19:15:28 7 Tiny change: 'e turn it into grid. Out' -> 'e turn it back into a grid. Out' (published)
en7 Английский mutsuki 2022-06-03 19:13:33 199 Tiny change: ':\n\no o o\no o o\n\' -> ':\n\no o o \no o o\n\'
en6 Английский mutsuki 2022-06-03 18:55:57 340
en5 Английский mutsuki 2022-06-03 18:54:46 355
en4 Английский mutsuki 2022-06-03 18:54:01 56
en3 Английский mutsuki 2022-06-03 18:52:55 64
en2 Английский mutsuki 2022-06-03 18:51:49 347
en1 Английский mutsuki 2022-06-03 18:51:00 1702 Initial revision (saved to drafts)