---
title: "Orientations, In/Out-Degree, Strong vs Weak"
summary: What changes when edges get arrows — and the degree identities that survive.
difficulty: easy
tags: [directed, definitions]
see: [directed/dag-toposort, directed/scc]
---

A digraph is $G = (V,E)$ with $E \subseteq V \times 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*.

:::definition label="Degrees"
$\deg^{+}(v)$ = number of edges leaving $v$; $\deg^{-}(v)$ = number entering.
$$\sum_v \deg^{+}(v) = \sum_v \deg^{-}(v) = m .$$
Balanced (or *Eulerian-oriented*) means $\deg^{+}(v) = \deg^{-}(v)$ for every $v$ — the exact condition behind @euler/euler-existence.
:::

:::proof
Count edges by their tail for the first identity, by their head for the second. Both equal $m$. ∎
:::

:::definition label="Connectivity, three levels"
- **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 \leadsto v$ *or* $v \leadsto u$.
- **strongly connected**: for every ordered pair $(u,v)$ a directed path $u \leadsto 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:

:::props title="After condensation (@directed/scc)"
- the condensation is a DAG ⟹ it has a topological order (@directed/dag-toposort),
- "can I reach $v$ from $u$?" = "$[u] \le [v]$ in the DAG" — answerable with bitset DP in $O(n^2/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:

:::theorem title="Strong orientation (Robbins)"
An undirected graph admits a strongly connected orientation $\iff$ it is connected and has no bridge.
:::

:::proof
$(\Rightarrow)$ A strongly connected digraph has no bridge (deleting any edge leaves an alternative directed route between its ends, hence connectivity).
$(\Leftarrow)$ Bridgeless connected $\implies$ 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.

:::example title="Balanced orientation"
$\deg^{+}(v) = \deg^{-}(v)$ for all $v$ is possible $\iff$ every degree is even $\iff$ $V$ splits into edge-disjoint cycles (an Eulerian decomposition). Orient each cycle consistently. This is why "even outdegree" problems reduce to @euler/hierholzer.
:::

:::figure src="Simple_Directed_Graph.svg" caption="A digraph with three SCCs; the condensation is the arrow between them, which is a DAG."
:::

```cpp out-in-deg.cpp
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 */ }
```

:::problems
- [[CSES 1682]] Flight Routes Check | https://cses.fi/problemset/task/1682 | core | strong connectivity
- [[CF 1385E]] Directing Edges | https://codeforces.com/problemset/problem/1385/E | core | orientation + toposort
- [[CSES 2179]] Even Outdegree Edges | https://cses.fi/problemset/task/2179 | hard | orientation, matching
:::