# Existence of a route following one-way streets

I am trying to understand the approach for this problem:

"If all streets are one way, there is still a legal way to drive from one intersection to another"

The question is to prove that it can be done in linear time. I am not looking for direct answers but the approach to this problem.

How can I think about this problem in terms of graph theory? AFAI understand, this will result in a DAG. But then should I choose BFS or DFS and why to prove it? (both are liner time algos)

• I will answer your comment regarding homework here: Everything is fine, there is no need to tag your question in any special way. See also our policy.
– Raphael
Jul 10, 2012 at 19:05
• Linear time in what? For example, BFS and DFS are not linear time in the number of nodes.
– Raphael
Jul 10, 2012 at 19:06
• in graph traversal, both are liner time algos right? $O(|V| + |E|)$? Jul 10, 2012 at 19:54
• @Raphael They are if the graph is planar, which is probably implied here. Jul 10, 2012 at 20:00
• @Raphael: Yes, but it's standard to call $O(n+m)$ "linear time" for graph algorithms, even if $m=\Theta(n^2)$, since the complexity of the input is $n+m$. Jul 11, 2012 at 19:54

First, it definitely won't result in a DAG, just a digraph. You need to get from A to B and B to A in order to satisfy your condition for nodes A and B, but that itself is a cycle.

Lots of time BFS and DFS are equivalent in relation to a problem, so it doesn't matter which one you choose. Here, the real trick is not choosing between DFS and BFS, but dealing with the fact that the graph is directed.

If you don't want a direct answer, here's the strategy I would use: first find a representation for the streets in terms of a digraph. What corresponds to edges? What corresponds to nodes?

Then, you need to find a graph algorithm that will work for this problem. What information do BFS and DFS give you about the graph? How can they be adapted to a directed graph?

To give you a little hint, I'd recommend you Google Eulerian chains.

As a hint, think about the intersections as nodes and the streets as directed edges connecting intersections. Then, try thinking about the following: find all clusters of nodes that are mutually reachable from one another (such nodes are said to be strongly-connected.

Hope this helps!