Functional Graph Structure
Every node has exactly one outgoing edge. That's it. One rule, and suddenly the graph has beautiful structure: tails feeding into cycles, shaped like the Greek letter rho. Functional graphs appear in hashing, random mappings, and a surprising number of competitive programming problems.
Definition
A functional graph on \(N\) nodes is defined by a function \(f: \{1, \ldots, N\} \to \{1, \ldots, N\}\). Each node \(i\) has exactly one outgoing edge to \(f(i)\). In-degree varies. Out-degree is always 1.
Think of it as "each person points to one other person." If you start at any node and keep following arrows, you must eventually revisit a node -- there are only \(N\) nodes. The moment you revisit, you've found a cycle.
The Rho Shape
Every weakly connected component of a functional graph looks like the letter \(\rho\):
Nodes 1, 7, 8 form a cycle. Nodes 2, 3, 4, 5, 6 are on "tails" that feed into the cycle. Once you enter the cycle, you loop forever.
Structural facts:
- Every component has exactly one cycle.
- Every node either sits on the cycle or on a tail leading to it.
- A node on the tail has in-degree 0 or more, but following \(f\) eventually leads to the cycle.
Key insight. Start at any node. Follow \(f\) repeatedly. You will enter a cycle within \(N\) steps. The path looks like a tail followed by a loop -- the rho shape. This structure makes functional graphs much more predictable than general directed graphs.
Finding Cycles: The Coloring DFS
To find all cycles, use a three-color DFS. White = unvisited. Gray = in the current path. Black = fully processed.
When you follow edges from a white node and hit a gray node, you've found a cycle. The cycle consists of all gray nodes from the repeated node onward.
vector<int> f(n + 1); // f[i] = successor of i
vector<int> cycleId(n + 1, 0);
vector<int> color(n + 1, 0); // 0=white, 1=gray, 2=black
for (int i = 1; i <= n; i++) {
if (color[i] != 0) continue;
vector<int> path;
int u = i;
while (color[u] == 0) {
color[u] = 1;
path.push_back(u);
u = f[u];
}
if (color[u] == 1) {
// Found a cycle starting at u
int len = 0;
int v = u;
do {
cycleId[v] = u; // mark cycle membership
color[v] = 2;
v = f[v];
len++;
} while (v != u);
}
// Mark remaining gray nodes as black (they're on tails)
for (int node : path) {
if (color[node] == 1) color[node] = 2;
}
}
CSES Planets Cycles
Problem. There are \(N\) planets. Each planet has a teleporter to exactly one other planet. For each planet, find how many teleportations are needed to return to the same planet.
If a planet is on a cycle of length \(L\), the answer is \(L\). If a planet is on a tail, you never return -- but wait, the problem says "the number of teleportations before visiting a planet you've visited before." Let me re-read. Actually, the CSES problem asks: for each planet, how many planets can you visit starting from it (counting itself) before revisiting one?
That's the tail length plus the cycle length. Follow from the node until you loop. The total unique nodes visited = tail length + cycle length.
Trace
Function: \(f = [-, 3, 5, 2, 3, 6, 5]\) (1-indexed, \(N = 6\)).
| Node | Path followed | Cycle found | Tail length | Cycle length | Answer |
|---|---|---|---|---|---|
| 1 | 1→3→2→5→6→5 | {5, 6} | 3 (nodes 1,3,2) | 2 (nodes 5,6) | 5 |
| 2 | 2→5→6→5 | {5, 6} | 1 (node 2) | 2 | 3 |
| 3 | 3→2→5→... | already known | 2 | 2 | 4 |
| 4 | 4→3→... | already known | 3 | 2 | 5 |
| 5 | on cycle | {5, 6} | 0 | 2 | 2 |
| 6 | on cycle | {5, 6} | 0 | 2 | 2 |
Implementation strategy:
- Find all cycles and their lengths.
- For cycle nodes, the answer is the cycle length.
- For tail nodes, BFS backward from cycle nodes, adding 1 to the answer at each step.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
vector<int> f(n + 1);
for (int i = 1; i <= n; i++) scanf("%d", &f[i]);
vector<int> ans(n + 1, 0);
vector<int> color(n + 1, 0);
vector<int> pos(n + 1, -1);
for (int i = 1; i <= n; i++) {
if (color[i] != 0) continue;
vector<int> path;
int u = i;
while (color[u] == 0) {
color[u] = 1;
pos[u] = path.size();
path.push_back(u);
u = f[u];
}
if (color[u] == 1) {
int cycLen = (int)path.size() - pos[u];
int v = u;
do {
ans[v] = cycLen;
color[v] = 2;
v = f[v];
} while (v != u);
}
// Process tail nodes in reverse
for (int j = (int)path.size() - 1; j >= 0; j--) {
if (ans[path[j]] == 0) {
ans[path[j]] = ans[f[path[j]]] + 1;
}
color[path[j]] = 2;
}
}
for (int i = 1; i <= n; i++) {
printf("%d%c", ans[i], " \n"[i == n]);
}
}
abc256_e: Takahashi's Anguish
Problem. \(N\) people each dislike exactly one other person. You want to seat them around a table. A person is unhappy if the person they dislike sits next to them. Find the minimum number of unhappy people.
Each person points to one other person -- a functional graph. The unhappy people come from cycles. In a cycle of length \(k\), you must break at least one "dislike" adjacency, so at least 1 person is unhappy per cycle.
Answer: the number of cycles in the functional graph.
Find cycles using the coloring DFS above. Count them.
Key insight. Tail edges can always be avoided in seating. Only cyclic constraints force an unavoidable conflict. Each cycle contributes exactly 1 to the answer.
abc357_e: Sanitize Hands
This is another functional graph structure problem. Each node follows one edge. The key is recognizing the functional graph and applying cycle-finding.
Complexity
Finding all cycles: \(O(N)\). Each node is visited at most twice (once in the forward pass, once in the backward propagation). Space: \(O(N)\).
Problems
| Problem | Link | Difficulty |
|---|---|---|
| CSES Planets Cycles | cses.fi/problemset/task/1751 | Medium |
| abc256_e Takahashi's Anguish | atcoder.jp/contests/abc256/tasks/abc256_e | Medium |
| abc357_e Sanitize Hands | atcoder.jp/contests/abc357/tasks/abc357_e | Medium |