Strong Orientation

A strong orientation of an undirected graph assigns a direction to every edge so the result is strongly connected: you can go from any vertex to any other along directed edges.

This lesson follows CP-Algorithms — Strong orientation.

When is it possible?

A bridge can be crossed in only one direction after orientation, so you cannot return. Hence a graph with a bridge has no strong orientation.

Robbins' theorem: an undirected graph has a strong orientation iff it is connected and bridgeless (2-edge-connected).

Construction (DFS)

On a bridgeless connected graph:

Run DFS; build a DFS tree.
Orient tree edges away from the root.
Orient every other edge from descendant toward ancestor (back / cross toward the tree).

Why it works: no bridges ⇒ after deleting any tree edge you can still climb using a path with a back edge. So every vertex can reach the root, and the root can reach every vertex via the tree → strongly connected.

Minimal number of SCCs

Orient so the digraph has as few SCCs as possible.

Handle each undirected component separately.
Bridges cannot sit inside a strong piece: after removing bridges you get bridgeless chunks you can strongly orient.
Orient bridges arbitrarily.

The algorithm below runs the same DFS orientation on each component: tree / back orientation plus bridge detection. Then

min #SCCs = (#undirected components) + (#bridges)

(each bridge merges into the count as an irreversible cut between otherwise strong pieces).

Implementation sketch

Bridge-finding DFS that also records an orientation when an edge is first used:

// adj: (neighbor, edge_id); edges[id] = {a,b} as in input
// orient[id] = '>' if directed a→b, '<' if b→a
void find_bridges(int v) {
    low[v] = tin[v] = time++;
    for (auto [nv, id] : adj[v]) {
        if (edge_used[id]) continue;
        edge_used[id] = true;
        orient[id] = (v == edges[id].first) ? '>' : '<';
        if (tin[nv] == -1) {
            find_bridges(nv);
            low[v] = min(low[v], low[nv]);
            if (low[nv] > tin[v]) bridge_cnt++;
        } else {
            low[v] = min(low[v], tin[nv]);
        }
    }
}
// answer: comp_cnt + bridge_cnt, and orient string

You can also orient first, then run any SCC algorithm to verify the count.

🧪 Orient a cycle vs a path

Check: strong orientation

Quiz