iii. Cycles and Functional Graphs

Detecting and extracting cycles in undirected and directed graphs, and the structure of functional graphs (every vertex has exactly one outgoing edge nxt[v]): each weak component is one directed cycle with in-trees hanging off it. Permutations, “next pointer” processes, iterated functions $x\mapsto f(x)$ and pseudo-random sequences are functional graphs. Shortest cycles (girth), minimum mean cycles and negative cycles are in Shortest Path Techniques and Shortest Paths.

Finding a cycle

• Undirected: DFS; a visited neighbour reached by an edge other than the one we came in on closes a cycle. Skip the parent edge id, not the parent vertex, or multi-edges are missed — a self-loop is a cycle by itself and needs no parent check at all. Alternatively, an edge whose endpoints are already connected in a DSU closes a cycle (this is also how Kruskal avoids cycles). A graph is a forest iff $m=n-c$.
• Directed: three colours; an edge to a grey vertex (on the current DFS path) is a back edge and closes a cycle. Edges to black vertices are harmless. Equivalently, Kahn’s algorithm leaves vertices unprocessed, or some SCC has size $>1$ — or size 1 with a self-loop, which Kahn’s/SCC-counting must also catch.

vector<int> findDirectedCycle(const vector<vector<int>>& g) {     // empty if acyclic
    int n = sz(g); vector<int> col(n), par(n, -1), cyc;
    auto dfs = [&](auto&& self, int u) -> bool {
        col[u] = 1;
        for (int v : g[u]) {
            if (col[v] == 1) { for (int x = u; x != v; x = par[x]) cyc.push_back(x); cyc.push_back(v); reverse(all(cyc)); return true; }
            if (!col[v]) { par[v] = u; if (self(self, v)) return true; }
        }
        col[u] = 2; return false;
    };
    for (int s = 0; s < n; s++) if (!col[s] && dfs(dfs, s)) return cyc;
    return {};
}

The cycle space of an undirected graph (edge sets with all degrees even, under XOR) has dimension $m-n+c$; the fundamental cycles of any spanning forest form a basis. That is why “XOR of a path” problems reduce to a tree path plus a linear basis of cycle XORs (Shortest Path Techniques, XOR Basis).

Proof: the cycle space has dimension $m-n+c$

Fix a spanning forest $F$ ($n-c$ edges). Each non-forest edge $e$ closes a unique fundamental cycle $C_e$ (with the forest path). These $m-n+c$ cycles are independent, since $C_e$ is the only one containing $e$. They span: for an even-degree edge set $S$, let $T=S\oplus {⨁}_{e\in S\setminus F}{C}_e$; it is still even-degree and uses only forest edges, but a nonempty even-degree subgraph contains a cycle, which a forest doesn’t have, so $T=\varnothing$.

Functional graphs

struct FunctionalGraph {
    int n, LOG = 1; vector<int> nxt, cycleOf, pos, tail, entry; vector<vector<int>> cycles, up;
    FunctionalGraph(const vector<int>& f) : n(sz(f)), nxt(f), cycleOf(n, -1), pos(n, -1), tail(n, -1), entry(n, -1) {
        while ((1 << LOG) <= n) LOG++;
        vector<int> st(n);
        for (int s = 0; s < n; s++) {
            if (st[s]) continue;
            vector<int> path; int v = s;
            while (!st[v]) st[v] = 1, path.push_back(v), v = nxt[v];
            if (st[v] == 1) {                                   // new cycle through v
                vector<int> cyc(find(all(path), v), path.end());
                for (int i = 0; i < sz(cyc); i++) cycleOf[cyc[i]] = sz(cycles), pos[cyc[i]] = i, tail[cyc[i]] = 0, entry[cyc[i]] = cyc[i];
                cycles.push_back(cyc);
            }
            for (int i = sz(path) - 1; i >= 0; i--) {
                int u = path[i]; st[u] = 2;
                if (tail[u] < 0) tail[u] = tail[nxt[u]] + 1, entry[u] = entry[nxt[u]], cycleOf[u] = cycleOf[nxt[u]];
            }
        }
        up.assign(LOG, nxt);
        for (int j = 1; j < LOG; j++) for (int v = 0; v < n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
    }
    int lift(int v, ll k) const { for (int j = 0; k; j++, k >>= 1) if (k & 1) v = up[j][v]; return v; }   // k < 2^LOG
    int jump(int v, ll k) const {                               // nxt applied k times, any k
        if (k <= tail[v]) return lift(v, k);
        int w = entry[v]; const auto& c = cycles[cycleOf[w]];
        return c[(pos[w] + (k - tail[v]) % sz(c)) % sz(c)];
    }
    ll dist(int u, int v) const {                               // min k with jump(u, k) == v, or -1
        if (cycleOf[u] != cycleOf[v]) return -1;
        if (!tail[v]) { int L = sz(cycles[cycleOf[v]]); return tail[u] + ((pos[v] - pos[entry[u]]) % L + L) % L; }
        if (tail[u] < tail[v]) return -1;
        return lift(u, tail[u] - tail[v]) == v ? tail[u] - tail[v] : -1;
    }
};

Typical uses: $k$-th successor for $k\le 10^{18}$ (CSES Planets Queries I), distance between two vertices (Planets Queries II), cycle length reached from each vertex (Planets Cycles), “after $k$ applications of a permutation”, simulation of deterministic processes with a small state space (find the period, then jump).

Task	Method
find the cycle from one start vertex	Floyd or Brent, $O(\mu +\lambda )$ time, $O(1)$ space
find all cycles over the whole graph	one colour-DFS / timestamp pass (the FunctionalGraph constructor above)
$k$-th successor, any single $k$	binary lifting, $O(\log k)$, or jump above in $O(1)$ after $O(n)$ preprocessing
cycle length only, no start point needed	the first phase of Brent’s algorithm alone suffices

Proof: the structure of functional graphs

Starting anywhere and following nxt, a finite graph forces a repeat, so every walk ends in a cycle. A weakly connected component can contain only one cycle: it has as many edges as vertices (one out-edge each), so its cycle space has dimension $m-n+1=1$. Every vertex reaches that cycle, and removing the cycle edges leaves in-trees rooted at the cycle vertices. Hence tail (distance to the cycle) and entry are well defined, and $u$ reaches $v$ iff they are in the same component and either $v$ is on the cycle (go to the entry, then around), or $v$ lies on $u$‘s tree path, i.e. $v$ is exactly ${\text{tail}}_u-{\text{tail}}_v$ steps ahead of $u$.

$O(1)$-memory cycle finding (implicit sequences)

For $x_{i+1}=f(x_i)$ with a huge state space (Pollard’s rho, PRNG periods): tail length $\mu$ and cycle length $\lambda$.

template<class T, class F> pair<ll, ll> brent(T x0, F f) {    // {mu, lambda}
    ll power = 1, lam = 1; T tort = x0, hare = f(x0);
    while (!(tort == hare)) { if (power == lam) tort = hare, power *= 2, lam = 0; hare = f(hare), lam++; }
    tort = hare = x0; for (ll i = 0; i < lam; i++) hare = f(hare);
    ll mu = 0; while (!(tort == hare)) tort = f(tort), hare = f(hare), mu++;
    return {mu, lam};
}

Floyd’s version: slow moves 1, fast moves 2 until they meet; then restart slow from $x_0$ and move both by 1; they meet at index $\mu$.

Proof: Floyd and Brent

$x_i=x_j$ with $i<j$ iff $i\ge \mu$ and $\lambda \mid j-i$.
Floyd: after $t$ steps the pointers are at $x_t$ and $x_{2t}$; they coincide iff $t\ge \mu$ and $\lambda \mid t$, which first happens at some $t\le \mu +\lambda$. Then $t\equiv 0(\mathrm{mod}\lambda )$, so walking $\mu$ more steps from $x_t$ lands on $x_{t+\mu }=x_{\mu }$, the same place the restarted pointer reaches after $\mu$ steps; before that they can’t meet since the restarted pointer is still in the tail.
Brent: in round $j$ the tortoise sits at index $2^j-1$ and the hare visits indices $2^j-1+\ell$ for $\ell =\mathrm{1..}{2}^j$. A match needs $2^j-1\ge \mu$ and $\lambda \mid \ell$; the first round with $2^j-1\ge \mu$ and $2^j\ge \lambda$ matches at $\ell =\lambda$, so lam $=\lambda$ exactly, and the total work is $O(\mu +\lambda )$. With the hare $\lambda$ steps ahead, $x_i=x_{i+\lambda }$ first holds at $i=\mu$.

Why Floyd uses speeds 1 and 2, not some other pair: once both pointers are inside the cycle, the gap between them (measured mod $\lambda$) changes by exactly $(\text{fast speed}-\text{slow speed})$ every step. With speeds $1,2$ the gap shrinks by exactly 1 each step, so it must hit 0 — a guaranteed meeting. With speeds $1,3$ (gap shrinks by 2) a cycle of even length can have the gap jump straight over 0 (e.g. $\lambda =6$: gaps $5,3,1,5,\dots$ or $4,2,0$ depending on parity — some starting offsets never land on 0). Any pair whose difference is coprime with every cycle length that can occur is safe; $1,2$ is simplest and always safe since the difference is 1.

Classic applications of Floyd/Brent beyond an explicit nxt array: duplicate detection in an array of values in $[0,n)$ by treating $i\to a_i$ as the functional graph (the duplicate is exactly the cycle’s entry point); the Happy Number problem (iterate digit-square-sum, a cycle means “not happy”); finding a linked list’s middle node as a byproduct of the slow/fast scan before reversing for a palindrome check.

Permutations as functional graphs

A permutation is a functional graph with in-degree 1: a disjoint union of cycles (no tails).

• The order of $p$ is the lcm of its cycle lengths; $p^k$ splits each cycle of length $L$ into $\gcd (L,k)$ cycles of length $L/\gcd (L,k)$.
• Parity of $p$ = parity of $n-(\text{number of cycles})$; minimum number of swaps to sort = $n-\text{cycles}$; minimum adjacent swaps = inversions.
• $k$-th roots: a cycle of length $M$ in $q$ becomes $\gcd (M,k)$ cycles of length $M/\gcd (M,k)$ in $q^k$. So $p$ has a $k$-th root iff, for every length $L$, the number of $L$-cycles of $p$ is a sum of admissible group sizes $g$, those with $\gcd (Lg,k)=g$ (interleave $g$ cycles of length $L$ into one of length $Lg$). For $k=2$: odd cycles are unrestricted, cycles of each even length must come in pairs.