DauChim's blog

Graph problem
By DauChim, history, 3 years ago, In English

Could u guys provide me a way to turn an undirected graph into directed graph by giving the directions for the egdes so the new graph is directed and doesn’t have any cycles

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

https://codeforces.net/blog/entry/68138 The blog is probably what you are looking for.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's an amazing blog btw, i readed it a few weeks ago and learned a lot.

    → Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Probably the simplest way is to direct each edge from the lower-valued node to the higher-valued node. There can't be any cycles because a cycle would imply that it's possible to get from a higher-valued node to a lower-valued one, but none of the edges are going to do that for you. Super dry solution, but it works :D

→ Reply