minimario's blog

Assistance for Timus 1077: Travelling Tours
By minimario, history, 9 years ago, In English

Hello all,

Today I will bring you some interesting problem: Oh, I forgot to mention I cannot solve it...Dx

So here is the problem. I guess I have some observation: that we have to consider the cycles in the graph. For example, in this graph here, we have 4 regions, and each region has an edge the other regions don't use. (Regions are coloured)

However, if I put new node 9 here, and try to colour like this:

But look it the problem here: if we try to use all 3 blue loops, then we cannot use the orange loop. So there is something tricky here.

So if anyone has any ideas or can provide some hints, I would really appreciate!

Thanks,

minimario

(P.S. If anyone want to continue solving Timus problem with me starting from 1077 and going down by difficulty, send me a message :))

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I guess user rsalesc has explained to me the solution, so I will present it here:

Find any DFS tree of the graph (say 1-2, 2-5, 5-8, 5-3, 3-4 in the graph above). Now, each of the other edges will make a cycle using only the tree edges and that edge. For each edge, we can make a cycle. And for each cycle, we need one of those other edges. Therefore, the answer is the total number of non-tree edges. We can find the cycles with DFS and backtracking.

→ Reply