siddhi's blog

Help needed in a question!
By siddhi, history, 5 years ago, In English

You are given a graph with some of its edges are directed and some are un-directed. You have to return true/false depending upon if you can convert all the undirected edges in directed ones such that there is no cycle in graph return true else return false..

Can some please some help on how to approach this problem?

Thanks in advance :)

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

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

If there is a directed cycle in the graph, then the answer is obviously NO.Otherwise answer is always YES. A construction can be made by induction. You keep on adding edges one by one, directing them arbitrarily, such that you don't form any cycle. suppose after adding k edges there is no cycle, but now both the directions that you direct the (k + 1)th edge will form a cycle, in this case you can remove the (k + 1) edge and these two cycles combined will form a bigger cycle. but that's contraditiction to our assumption that there were no cycle until k edges.

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

    Thank you pshishod2645. I was able to come with this approach but was not able to come with some concrete proof for this. Thank you once again for helping me out.

    → Reply