Register

CMI2016-B-3

• edited by
1,215 views
2 2 votes

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.

2 Answers

Best answer
4 4 votes
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)$
• selected by
Voting & Accepting an answer helps improve the community
← Previous · PipelineNext → · pipeLine
← Previous in category · CMI2016-B-2bNext in category → · A graph $G$ is Euler...
Position:
Show:

Related questions

1 1 vote
1 1 answer
869
869 views
go_editor asked Dec 30, 2016
869 views
CMI2016-B-2b
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $length$ of such a path (respectively ...
1 1 vote
2 2 answers
980
980 views
go_editor asked Dec 30, 2016
980 views
CMI2016-B-2a
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $\textit{length}$ of such a path (resp...
2 2 votes
2 answers 2 answers
1.3k
1.3k views
go_editor asked Dec 30, 2016
1,328 views
CMI2016-A-9
ScamTel has won a state government contract to connect $17$ cities by high-speed fibre optic links. Each link will connect a pair of cities so that the entire network is ...
2 2 votes
2 answers 2 answers
938
938 views
go_editor asked Dec 30, 2016
938 views
CMI2016-A-5
A dodecahedron is a regular solid with $12$ faces, each face being a regular pentagon. How many edges are there? And how many vertices?$60$ edges and $20$ vertices$30$ ed...