Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

DauChim's blog

Graph problem
By DauChim, history, 5 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

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

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

→ Reply
»
5 years ago, hide # |
 
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