---
title: "Functional and Permutation Graphs"
summary: One out-edge per vertex: cycles with trees hanging off them, and the binary-lifting that navigates them.
difficulty: core
tags: [functional graph, lifting, cycles]
time: n
prereq: [structures/dsu, lca/binary-lifting]
see: [lca/binary-lifting, directed/cycles]
---

A **functional graph** is a digraph where every vertex has out-degree exactly 1: $f: V \to 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.

:::theorem title="Structure"
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).
:::

:::proof
Start anywhere and iterate $f$: after at most $n+1$ steps a vertex repeats, giving a closed walk $x, f(x), \dots, f^{k}(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.

```cpp functional-cycles.cpp
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 lengths
```

The 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).

```cpp depth-to-cycle.cpp
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/binary-lifting: $\operatorname{up}[v][j] = f^{2^j}(v)$.

```cpp jump.cpp
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 k
```

:::note title="Why the modulus is legal"
Once you reach a cycle of length $L$, $f^{k}(v)$ depends on $k \bmod L$. So $k \le 10^{18}$ 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(\mu + \lambda)$ time and $O(1)$ memory.
:::

:::figure src="Permutation_Graph.svg" caption="A permutation on 12 elements: three disjoint directed cycles, which is the entire structure — decomposing into these is O(n) and answers most permutation questions."
:::

:::example title="Inverting a permutation"
Write the cycles; the inverse is each cycle reversed. To get $f^{k}$ for huge $k$ as a *permutation* (not a query), rotate each cycle by $k \bmod L$: $O(n)$, and this is the standard trick for "apply the shuffle $10^9$ times".
:::

:::problems
- [[CSES 1750]] Planets Queries I | https://cses.fi/problemset/task/1750 | core | binary lifting
- [[CSES 1751]] Planets Cycles | https://cses.fi/problemset/task/1751 | core | peel + cycle id
- [[CF 25D]] Roads not only in Berland | https://codeforces.com/problemset/problem/25/D | easy | DSU on a functional model
:::