Pattern Guide
Functional Graphs
"Every node has exactly one outgoing edge. Each component = rho (ρ) shape: tail + cycle."
A functional graph has exactly one outgoing edge per node (each node maps to exactly one other node). Every connected component has a unique structure: a "rho" shape — a tail leading into a cycle. Applications: cycle detection in single-linked structures, finding k-th element in an iterated function sequence, counting cycles in permutations, and periodic sequence analysis.
Problems you can solve with this pattern
3 problems · click any to start solving
// Analyze functional graph f: each f[i] = successor of node i
function analyzeFunctionalGraph(n, f) {
const onCycle = new Array(n).fill(false);
const visited = new Array(n).fill(0); // 0=unvisited, 1=in progress, 2=done
const cycleId = new Array(n).fill(-1);
const cycles = [];
function dfs(start) {
const path = [];
let u = start;
while (visited[u] === 0) {
visited[u] = 1;
path.push(u);
u = f[u];
}
if (visited[u] === 1) {
// Found a cycle — extract it from path
const cycleStart = path.indexOf(u);
const cycle = path.slice(cycleStart);
const cid = cycles.length;
cycles.push(cycle);
for (const v of cycle) { onCycle[v] = true; cycleId[v] = cid; }
}
for (const v of path) visited[v] = 2;
}
for (let i = 0; i < n; i++) if (!visited[i]) dfs(i);
return { onCycle, cycleId, cycles };
}
// Binary lifting: compute f^k(x) in O(log k) after O(n log MAX_K) preprocessing
function buildLifting(n, f, maxK) {
const LOG = Math.ceil(Math.log2(maxK + 1)) + 1;
const anc = Array.from({length: n}, (_, i) => [f[i]]);
for (let j = 1; j < LOG; j++)
for (let i = 0; i < n; i++)
anc[i].push(anc[anc[i][j-1]][j-1]);
return {
kthIterate: (x, k) => {
for (let j = 0; k > 0; j++, k >>= 1)
if (k & 1) x = anc[x][j];
return x;
}
};
}In a functional graph f: [n]→[n], each connected component has exactly one cycle (the "loop" of the rho). Detect cycles: DFS coloring (unvisited/in-stack/done) or Floyd's algorithm. Find k-th iterate f^k(x): binary lifting — precompute f^(2^j)(x) for j = 0..log(k), then compose to get f^k(x) in O(log k). Count element types: nodes on cycles vs nodes on tails.
// Analyze functional graph f: each f[i] = successor of node i
function analyzeFunctionalGraph(n, f) {
const onCycle = new Array(n).fill(false);
const visited = new Array(n).fill(0); // 0=unvisited, 1=in progress, 2=done
const cycleId = new Array(n).fill(-1);
const cycles = [];
function dfs(start) {
const path = [];
let u = start;
while (visited[u] === 0) {
visited[u] = 1;
path.push(u);
u = f[u];
}
if (visited[u] === 1) {
// Found a cycle — extract it from path
const cycleStart = path.indexOf(u);
const cycle = path.slice(cycleStart);
const cid = cycles.length;
cycles.push(cycle);
for (const v of cycle) { onCycle[v] = true; cycleId[v] = cid; }
}
for (const v of path) visited[v] = 2;
}
for (let i = 0; i < n; i++) if (!visited[i]) dfs(i);
return { onCycle, cycleId, cycles };
}
// Binary lifting: compute f^k(x) in O(log k) after O(n log MAX_K) preprocessing
function buildLifting(n, f, maxK) {
const LOG = Math.ceil(Math.log2(maxK + 1)) + 1;
const anc = Array.from({length: n}, (_, i) => [f[i]]);
for (let j = 1; j < LOG; j++)
for (let i = 0; i < n; i++)
anc[i].push(anc[anc[i][j-1]][j-1]);
return {
kthIterate: (x, k) => {
for (let j = 0; k > 0; j++, k >>= 1)
if (k & 1) x = anc[x][j];
return x;
}
};
}Rho (ρ) shape: Named after the Greek letter — a tail leading into a cycle.
Key operations:
- Cycle detection: Floyd's (O(n)) or DFS coloring (O(n))
- Find cycle entry: Floyd's phase 2
- k-th iterate: binary lifting O(n log k) preprocessing, O(log k) per query
- Count nodes on cycles vs tails: topological sort (tails have zero in-degree in functional graph)
Applications: Permutation cycle structure, birthday paradox, Pollard's rho factorization, iterated hash functions.