Chapter 3 · Directed Graphs
Orientations, In/Out-Degree, Strong vs Weak
What changes when edges get arrows — and the degree identities that survive.
A digraph is G = (V,E) with E ⊆ V × V: ordered pairs, so uv and vu are different edges. Nothing else about the vocabulary changes, and that is a trap — almost every undirected intuition needs one extra word: weakly or strongly.
deg+(v) = number of edges leaving v; deg-(v) = number entering.
Balanced (or Eulerian-oriented) means deg+(v) = deg-(v) for every v — the exact condition behind Euler Tours: When They Exist.
Count edges by their tail for the first identity, by their head for the second. Both equal m. ∎
- weakly connected: connected after forgetting directions (equivalently, the underlying undirected graph is connected).
- unilaterally connected: for every u,v there is a directed path u ⇝ v or v ⇝ u.
- strongly connected: for every ordered pair (u,v) a directed path u ⇝ v.
Strong ⟹ unilateral ⟹ weak, and each implication is strict: a directed 3-cycle is strong; two strongly connected cycles joined by a single arrow are unilateral but not strong; an undirected path viewed as a digraph is only weak.
#Reachability is a partial order (after condensing)
Reachability in a digraph is reflexive and transitive, but not symmetric — a preorder. Collapse each set of mutually reachable vertices (a strongly connected component) and you get an honest partial order on the components. Everything you can do with "≤" becomes available:
After condensation (Strongly Connected Components)
- the condensation is a DAG ⟹ it has a topological order (DAGs and Topological Order),
- "can I reach v from u?" = "[u] ≤ [v] in the DAG" — answerable with bitset DP in O(n2/64) per vertex set,
- a DAG with a Hamilton path has a unique topological order, and conversely: consecutive-in-order edges exist ⟹ Hamilton path (the standard linear test),
- in-degrees and out-degrees of components decide the "minimum number of paths covering all vertices"-style answers.
#Orientation problems
"Given an undirected graph, direct the edges so that …" is a whole genre, and the answers are always the same two facts:
An undirected graph admits a strongly connected orientation ⇔ it is connected and has no bridge.
(⇒) A strongly connected digraph has no bridge (deleting any edge leaves an alternative directed route between its ends, hence connectivity). (⇐) Bridgeless connected ⇒ every edge lies on a cycle; decompose G into its 2-edge-connected blocks and orient each block along an ear decomposition (start with a cycle oriented cyclically, add each ear as a directed path between its already-oriented endpoints). Result: strongly connected. ∎
The algorithmic version is 12 lines: find bridges, then for each 2-edge-connected component run the ear-based orientation, or equivalently output the bridge-less DFS order and orient tree edges downward and back edges upward.
deg+(v) = deg-(v) for all v is possible ⇔ every degree is even ⇔ V splits into edge-disjoint cycles (an Eulerian decomposition). Orient each cycle consistently. This is why "even outdegree" problems reduce to Hierholzer's Linear Algorithm.
vector<int> ind(n), outd(n);
for (auto [u, v] : edges) { outd[u]++; ind[v]++; }
for (int i = 0; i < n; i++) if (ind[i] != outd[i]) { /* needs an added edge / not Eulerian */ }