# Algorithm to convert undirected connected graph with no bridges to strongly connected directed graph [duplicate]

I am not sure how to go about this exactly. My attempt is find the pick an arbitrary node and run DFS, ordering each node by order of discovery. After this, You can orient each of edges so it pointing from lower order to higher order. Now I know this will create a path from one node to another, but doesn't guarantee a path from the other back to the initial. Is there any way to modify my algorithm so that it it would strongly connected and not just connected.

Proof. Let $$\mathcal{C}$$ be the strongly connected components of the resulting graph. Let $$\mathcal{G}$$ be the DAG resulting from contracting the vertices in each component in $$\mathcal{C}$$. Also, let $$C_0 \in \mathcal{C}$$ be the strongly connected component containing $$r$$. We have to prove that $$C_0$$ is the only component in $$\mathcal{C}$$ and hence, it contains all the vertices in the graph. Assuming otherwise, all components must be reachable from $$C_0$$ in $$\mathcal{G}$$, since all vertices are reachable from $$r$$ in $$G$$. choose $$C$$ to be a component in $$\mathcal{C}$$ that is the end of a longest path $$P$$ from $$C_0$$ in $$\mathcal{G}$$. Let $$C'$$ be the component previous to $$C$$ on that path. There is an edge from a vertex in $$C'$$ to a vertex in $$C$$. But this edge is not a bridge, hence, there must be an edge leaving $$C$$ and directed from $$C$$ to outside $$C$$ (since such an edge must have been discovered the first time we visited $$C$$). If this edge goes to a component $$C''$$ not on $$P$$, we could have extended $$P$$ to $$C''$$ resulting in a longer path wich is a contradiction. On the other hand, if it goes to a component on $$P$$, it forms a cycle, which contradicts the assumption that $$\mathcal{G}$$ is the DAG over the SCCs of the graph we build from $$G$$ and hence cannot have cycles. Hence, $$\mathcal{C}$$ cannot have more than one component, namely $$C_0$$.
• Thanks, this looks better. I had to think about the claim that some edge leaving $C$ is necessarily directed from $C$ to outside $C$: Suppose to the contrary that all such edges are directed the other way, and there is at least 1 such edge. Call these edges $F$. Let $uv$ be the edge from $C'$ to $C$. ... Dec 30 '19 at 13:40
• ... After visiting $v$, DFS will not backtrack to a vertex it discovered before $u$ until it has visited all vertices reachable from $v$, which includes at least all vertices in $C$ and their neighbours, so each edge in $F$ is discovered at the end of a directed path starting at $v$ -- which must have left $C$ before returning via the edge in $F$. Since $|F|\ge 1$, some edge leaves $C$. Dec 30 '19 at 13:40