Strong Orientation

Given an undirected graph, can you assign a direction to each edge so that the result is strongly connected (every vertex reaches every other)?

Robbins’ theorem

A connected undirected graph has a strong orientation iff it is bridgeless (2-edge-connected).

Necessity. If $e$ is a bridge, orienting it one way makes the far side unreachable, and orienting it the other way makes the near side unreachable. Either way strong connectivity fails.

Sufficiency (constructive). Run a DFS. Orient every tree edge from parent to child (downward) and every back edge from descendant to ancestor (upward). In a bridgeless graph every vertex has a back edge reaching strictly above it, so you can always climb to the root and descend to anywhere. ∎

Construction

int timer_ = 0;
vector<int> tin;
vector<pair<int,int>> oriented;
 
void dfs(int u, int pe) {
    tin[u] = ++timer_;
    for (auto [v, id] : adj[u]) {
        if (id == pe) continue;
        if (!tin[v]) { oriented.push_back({u, v}); dfs(v, id); }   // tree edge: down
        else if (tin[v] < tin[u]) oriented.push_back({u, v});      // back edge: up
    }
}

Only orient each edge once — the tin[v] < tin[u] guard ensures a back edge is handled from the deeper endpoint, not both ends.

Mixed graphs

When some edges are already directed and others are free, the question becomes harder but is still polynomial: it reduces to a flow feasibility problem (Boesch-Tindell). Model each undirected edge as contributing $\pm 1$ to the degree balance and solve a circulation with demands.

Generalisation: Nash-Williams

Every $2k$-edge-connected undirected graph has a $k$-arc-connected orientation.

Robbins’ theorem is the case $k=1$. This is the reason “make the road network one-way but keep everything reachable” problems always start by checking for bridges.

What to do when bridges exist

If the graph has bridges, no strong orientation exists — but the useful answer is usually structural rather than a flat “no”:

1. Build the bridge tree.
2. Each 2-edge-connected component can be strongly oriented internally.
3. The bridges must be oriented, and their directions form a tree orientation — so the reachability structure is exactly the bridge tree with a chosen orientation.
4. To make a strong orientation possible, add $\lceil L/2\rceil$ edges where $L$ is the number of leaves of the bridge tree.

Typical problems

• “Make every street one-way, keep the city connected” — the classic statement; answer: possible iff bridgeless.
• “Minimum edges to add so a one-way system exists” — $\lceil L/2\rceil$ on the bridge tree.
• Orient edges to maximise the number of reachable pairs — condense with the bridge tree, then a tree DP.
• Orient edges so every vertex has a given in-degree — a flow problem, not Robbins.

See also: Bridge Tree · Bridges · SCC