Chapter 3 · Directed Graphs
Functional and Permutation Graphs
One out-edge per vertex: cycles with trees hanging off them, and the binary-lifting that navigates them.
A functional graph is a digraph where every vertex has out-degree exactly 1: f: V → V. A permutation graph additionally has in-degree 1 (so f is a bijection). These are not curiosities — "each node points to its parent", "each planet has exactly one outgoing teleporter", "each cell moves to the next cell" are all functional graphs, and they are the reason binary lifting is in every template.
Every weakly connected component of a functional graph is exactly one directed cycle with rooted in-trees hanging off its vertices (edges pointing toward the cycle).
Start anywhere and iterate f: after at most n+1 steps a vertex repeats, giving a closed walk x, f(x), …, fk(x) = x; minimality of the first repeat makes these k vertices distinct, so they form a cycle C. Every vertex reaches C (same argument), and out-degree 1 means once you are on C you never leave. Contract C to a root: the remaining edges give each vertex one parent, so each attached part is a tree oriented toward the root. ∎
For a permutation, in-degree 1 too, so the "hanging trees" are absent: a permutation graph is a disjoint union of directed cycles. That single sentence is why permutation problems are cycle problems.
#Three tasks, three linear algorithms
Every task below is linear, and the first one unlocks the other two.
vector<int> indeg(n);
for (int u = 0; u < n; u++) indeg[f[u]]++;
queue<int> q;
for (int i = 0; i < n; i++) if (!indeg[i]) q.push(i);
vector<char> cyc(n, 1);
while (!q.empty()) {
int u = q.front(); q.pop();
cyc[u] = 0;
if (--indeg[f[u]] == 0) q.push(f[u]);
}
// cyc[u] == 1 for exactly the vertices on cycles; walk them to get the lengthsThe other two questions reuse the peel: depth to the cycle (reverse the edges, BFS outward from the cycle vertices — gives both the distance and the identity of the cycle you fall into) and reachability after k steps (lifting, below).
vector<vector<int>> rad(n); // reversed edges
for (int u = 0; u < n; u++) if (!cyc[u]) rad[f[u]].push_back(u);
queue<int> qq;
vector<int> dep(n, 0), cid(n, -1);
for (int v = 0; v < n; v++) if (cyc[v] && cid[v] == -1) {
int c = nxt_cid++, len = 0, x = v;
do { cid[x] = c; dep[x] = 0; qq.push(x); x = f[x]; len++; } while (x != v);
while (!qq.empty()) { // grow trees off the cycle
int u = qq.front(); qq.pop();
for (int w : rad[u]) { cid[w] = c; dep[w] = dep[u] + 1; qq.push(w); }
}
cycle_len[c] = len;
}#Navigating with lifting
"Where am I after k steps?" is the same jump-pointer idea as LCA by Binary Lifting: up[v][j] = f2j(v).
const int LOG = 20; // 2^20 > 10^6 steps
vector<array<int, LOG>> up(n);
for (int v = 0; v < n; v++) up[v][0] = f[v];
for (int j = 1; j < LOG; j++)
for (int v = 0; v < n; v++) up[v][j] = up[up[v][j-1]][j-1];
int jump(int v, int k) {
for (int j = 0; j < LOG; j++) if (k >> j & 1) v = up[v][j];
return v;
}
// pre O(n log n), query O(log n); cycle length L => reduce k mod L for huge kOnce you reach a cycle of length L, fk(v) depends on k mod L. So k ≤ 1018 is not a big-integer problem: find the entry point, the pre-period length, and L — all with the peel above or Floyd's tortoise-and-hare in O(μ + λ) time and O(1) memory.
Write the cycles; the inverse is each cycle reversed. To get fk for huge k as a permutation (not a query), rotate each cycle by k mod L: O(n), and this is the standard trick for "apply the shuffle 109 times".