CMI2016-B-3

Question

An undirected graph can be converted into a directed graph by choosing a direction for every edge. Here is an example:

Show that for every undirected graph, there is a way of choosing directions for its edges so that the resulting directed graph has no directed cycles.

Answer 1

Select any random vertex and start BFS algorithm such that if you are at vertex $u$ and going to vertex $v$ direction of the edge will be from $u$ to $v, u\rightarrow v.$ Maintain a data structure $\text{visited[i]}$ which keeps track of unvisited edge -- if the edge $e_k$ is visited we do not perform BFS. This will create a directed graph with no back edge. Complexity -- $O(V+E)$

Answer 2