Блог пользователя DauChim

Graph problem
Автор DauChim, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

→ Ответить