These are the notes for Competitive Programming episode 57. A functional graph (also called a successor graph) is a directed graph in which every vertex has exactly one outgoing edge, so the edges are just a function f: the next vertex of v is f(v). Every walk in it eventually repeats, so it is a tail followed by a loop (the ρ, "rho", shape), and every connected piece has exactly one cycle with trees hanging into it. Rumour Reach asks, for every student, how many students a rumour reaches: walking from everyone is Time Limit Exceeded on a chain of 2 · 10^5; one walk per vertex with three states is O(n), while two states (treating "finished" as "on my walk") prints 1 where 5 is right. Teleport Gates asks where you are after k ≤ 10^18 jumps: a jump table with 30 levels prints 2 where 4 is right; 60 levels is accepted. Lucky Number Machine finds the tail and loop of x → (x² + c) mod m with Floyd's tortoise and hare in O(1) memory, where a map stores 1,140,378 numbers. Stress tests pass. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
In a hostel, every student has one best friend they tell everything to. Start a rumour with any student and follow it: student → friend → friend's friend → … With 8 students, after 9 tellings there have been 9 hearings among 8 people, so somebody heard it twice (the pigeonhole principle). From that moment the rumour goes round the same group of friends forever, because each student always tells the same friend. So every rumour path is a straight tail and then a loop. And if student i tells student j, everyone j's rumour reaches, i's rumour reaches too: we can reuse j's answer.
What a functional graph looks like
- n vertices, n edges, out-degree exactly 1 everywhere (f(i) = i, a self-loop, is allowed).
- Each connected piece (ignoring edge directions) has exactly one cycle. Vertices not on a cycle form trees whose edges point towards the cycle.
- From any start x, the sequence x, f(x), f(f(x)), … is μ tail vertices followed by a cycle of length λ (μ ≥ 0, λ ≥ 1). μ + λ ≤ n.
- The same picture appears whenever "the next state" is a function of the current one: a pseudo-random generator, a permutation, a game position with one move, a linked list that may loop.
Problem E1 · Rumour Reach
(Written for this course, in the style of a Codeforces Div. 2 C/D problem.)
n students; student i always tells student f[i]. For every student i, print how many different students hear a rumour that i starts (i included).
- Input: n (1 ≤ n ≤ 2 · 10^5), then f[1 … n] (1 ≤ f[i] ≤ n).
- Output: n numbers.
8
2 3 4 2 4 7 6 1
8 → 1 → 2 → 3 6 ⇄ 7
↑ ↓
5 → 4 ←─┘
The loops are 2 → 3 → 4 → 2 and 6 ⇄ 7. 8 → 1 → 2 and 5 → 4 are tails. Answers: 4 3 3 3 4 2 2 5.
The obvious attempt: walk from every student (TLE)
Follow the arrows from s and count until a student repeats. seenAt[v] = s marks v as visited by walk s, so the array never has to be cleared.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, f[200001], seenAt[200001];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> f[i];
for (int s = 1; s <= n; s++) { // walk from every student
int cnt = 0, v = s;
while (seenAt[v] != s) { // stop at the first repeat
seenAt[v] = s;
cnt++;
v = f[v];
}
cout << cnt << " \n"[s == n];
}
}
4 3 3 3 4 2 2 5
On the chain 1 → 2 → … → n → n (n = 2 · 10^5), student 1 walks n steps, student 2 walks n − 1, and so on: n² / 2 ≈ 2 · 10^10 steps.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, f[200001], seenAt[200001];
int main() {
n = 200000; // a long chain 1 -> 2 -> ... -> n -> n
for (int i = 1; i < n; i++) f[i] = i + 1;
f[n] = n;
ll total = 0;
for (int s = 1; s <= n; s++) { // walk from every student
int cnt = 0, v = s;
while (seenAt[v] != s) { // stop at the first repeat
seenAt[v] = s;
cnt++;
v = f[v];
}
total += cnt;
}
cout << total << "\n";
}
Time Limit Exceeded
The observation: loops first, then tails
- On a loop of length L, every student on it reaches exactly the L students of the loop.
- On a tail,
ans[i] = ans[f[i]] + 1: i's rumour reaches i itself plus everything f[i]'s rumour reaches (i is not among them, because i is not on a loop).
So find every loop once and fill tails from the loop outwards.
One walk per student: three states
Walk from s, pushing students on path and remembering pos[v] (where v sits on the path), until reaching a student already seen. "Seen" must be split in two:
| state | meaning | what reaching it means |
|---|---|---|
| 0 | not seen yet | keep walking |
| 1 | on this walk | we came back to our own path: a new loop, of length path.size() − pos[v] |
| 2 | finished earlier | no new loop; v already has an answer |
After handling a new loop, fill the rest of the path back to front with ans[u] = ans[f[u]] + 1. Every student enters a path once, so the whole thing is O(n).
The bug: two states instead of three
Checking if (state[v]) treats a finished student as if it were on the current walk. Student 8's walk stops at student 1 (finished on an earlier walk), and the code "finds" a loop of length 1 − pos[1] = 1:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, f[200001], state[200001], pos[200001], ans[200001];
// state: 0 = not seen, 1 = on the current walk, 2 = finished
void solve() {
for (int s = 1; s <= n; s++) {
if (state[s]) continue;
vector<int> path;
int v = s;
while (state[v] == 0) { // walk until we meet something seen
state[v] = 1;
pos[v] = path.size();
path.push_back(v);
v = f[v];
}
if (state[v]) { // back on our own walk: a new loop
int L = path.size() - pos[v];
for (int i = pos[v]; i < (int)path.size(); i++) ans[path[i]] = L, state[path[i]] = 2;
path.resize(pos[v]);
}
for (int i = (int)path.size() - 1; i >= 0; i--) { // the tail, back to front
int u = path[i];
ans[u] = ans[f[u]] + 1;
state[u] = 2;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> f[i];
solve();
for (int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
}
4 3 3 3 4 2 2 1
Student 8 should reach 5, not 1. The fix is state[v] == 1:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, f[200001], state[200001], pos[200001], ans[200001];
// state: 0 = not seen, 1 = on the current walk, 2 = finished
void solve() {
for (int s = 1; s <= n; s++) {
if (state[s]) continue;
vector<int> path;
int v = s;
while (state[v] == 0) { // walk until we meet something seen
state[v] = 1;
pos[v] = path.size();
path.push_back(v);
v = f[v];
}
if (state[v] == 1) { // back on our own walk: a new loop
int L = path.size() - pos[v];
for (int i = pos[v]; i < (int)path.size(); i++) ans[path[i]] = L, state[path[i]] = 2;
path.resize(pos[v]);
}
for (int i = (int)path.size() - 1; i >= 0; i--) { // the tail, back to front
int u = path[i];
ans[u] = ans[f[u]] + 1;
state[u] = 2;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> f[i];
solve();
for (int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
}
4 3 3 3 4 2 2 5
A single student who talks to himself (a loop of length 1):
1
The 2 · 10^5 chain (the answers add up to n(n + 1) / 2):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, f[200001], state[200001], pos[200001], ans[200001];
// state: 0 = not seen, 1 = on the current walk, 2 = finished
void solve() {
for (int s = 1; s <= n; s++) {
if (state[s]) continue;
vector<int> path;
int v = s;
while (state[v] == 0) { // walk until we meet something seen
state[v] = 1;
pos[v] = path.size();
path.push_back(v);
v = f[v];
}
if (state[v] == 1) { // back on our own walk: a new loop
int L = path.size() - pos[v];
for (int i = pos[v]; i < (int)path.size(); i++) ans[path[i]] = L, state[path[i]] = 2;
path.resize(pos[v]);
}
for (int i = (int)path.size() - 1; i >= 0; i--) { // the tail, back to front
int u = path[i];
ans[u] = ans[f[u]] + 1;
state[u] = 2;
}
}
}
int main() {
n = 200000; // a long chain 1 -> 2 -> ... -> n -> n
for (int i = 1; i < n; i++) f[i] = i + 1;
f[n] = n;
solve();
ll total = 0;
for (int i = 1; i <= n; i++) total += ans[i];
cout << total << "\n";
}
20000100000
Stress test against the brute force
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, f[200001], state[200001], pos[200001], ans[200001];
// state: 0 = not seen, 1 = on the current walk, 2 = finished
void solve() {
for (int s = 1; s <= n; s++) {
if (state[s]) continue;
vector<int> path;
int v = s;
while (state[v] == 0) { // walk until we meet something seen
state[v] = 1;
pos[v] = path.size();
path.push_back(v);
v = f[v];
}
if (state[v] == 1) { // back on our own walk: a new loop
int L = path.size() - pos[v];
for (int i = pos[v]; i < (int)path.size(); i++) ans[path[i]] = L, state[path[i]] = 2;
path.resize(pos[v]);
}
for (int i = (int)path.size() - 1; i >= 0; i--) { // the tail, back to front
int u = path[i];
ans[u] = ans[f[u]] + 1;
state[u] = 2;
}
}
}
int seenAt[200001];
int brute(int s) {
int cnt = 0, v = s;
while (seenAt[v] != s) seenAt[v] = s, cnt++, v = f[v];
return cnt;
}
int main() {
mt19937 rng(57);
for (int t = 1; t <= 500; t++) {
n = rng() % 10 + 1;
for (int i = 1; i <= n; i++) f[i] = rng() % n + 1, state[i] = 0, seenAt[i] = 0;
solve();
for (int i = 1; i <= n; i++)
if (ans[i] != brute(i)) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 500 tests passed";
}
all 500 tests passed
Problem E2 · Teleport Gates
(Written for this course.)
n gates; entering gate i sends you to gate f[i], and you are pulled into the next one at once. q queries (x, k): where are you after exactly k jumps from gate x?
- Input: n q (n, q ≤ 2 · 10^5), f[1 … n], then q lines x k (0 ≤ k ≤ 10^18).
- Output: one gate per query.
8 3
2 3 4 2 4 7 6 1
8 3
5 4
6 7
The obvious attempt: one jump at a time (TLE)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q, f[200001];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> f[i];
while (q--) {
int x;
ll k;
cin >> x >> k;
while (k--) x = f[x]; // one jump at a time
cout << x << "\n";
}
}
3
4
7
With k = 10^18 it never finishes (10^18 jumps ≈ 30 years at 10^9 per second):
8 3
2 3 4 2 4 7 6 1
8 3
6 1000000000000000000
1 777777777777777777
Time Limit Exceeded
Jump tables (binary lifting on a functional graph)
up[j][v] = the gate you reach after 2^j jumps from v. up[0][v] = f[v], and 2^j jumps are 2^(j−1) jumps twice: up[j][v] = up[j−1][up[j−1][v]]. To make k jumps, write k in binary and use up[j] for every set bit j. This is the LCA table of episode 53, but simpler: every vertex has a next vertex, so there is no root and no −1.
How many levels? Enough that 2^LOG > max k. For k ≤ 10^18, LOG = 60 (2^60 ≈ 1.15 · 10^18).
The bug: too few levels
With LOG = 30 the bits of k above bit 29 are ignored:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int LOG = 30; // 2^30 is about a billion
int n, q, up[LOG][200001]; // up[j][v]: where 2^j jumps from v land
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> up[0][i];
for (int j = 1; j < LOG; j++)
for (int v = 1; v <= n; v++)
up[j][v] = up[j - 1][up[j - 1][v]]; // 2^j = 2^(j-1), twice
while (q--) {
int x;
ll k;
cin >> x >> k;
for (int j = 0; j < LOG; j++)
if (k >> j & 1) x = up[j][x]; // use the bits of k
cout << x << "\n";
}
}
3
6
2
The last answer should be 4. (The middle one is right only by luck: 6 is on a loop of length 2 and the ignored part of k is even.) With 60 levels:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int LOG = 60; // 2^60 > 10^18
int n, q, up[LOG][200001]; // up[j][v]: where 2^j jumps from v land
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> up[0][i];
for (int j = 1; j < LOG; j++)
for (int v = 1; v <= n; v++)
up[j][v] = up[j - 1][up[j - 1][v]]; // 2^j = 2^(j-1), twice
while (q--) {
int x;
ll k;
cin >> x >> k;
for (int j = 0; j < LOG; j++)
if (k >> j & 1) x = up[j][x]; // use the bits of k
cout << x << "\n";
}
}
3
6
4
Check: gate 1 → 2 is one jump, then 777777777777777776 jumps on the loop 2 → 3 → 4 (length 3); 777777777777777776 mod 3 = 2, so 2 → 3 → 4.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int LOG = 60;
int n, f[200001], up[LOG][200001];
int main() {
mt19937_64 rng(57);
for (int t = 1; t <= 500; t++) {
n = rng() % 10 + 1;
for (int i = 1; i <= n; i++) up[0][i] = f[i] = rng() % n + 1;
for (int j = 1; j < LOG; j++)
for (int v = 1; v <= n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
int x = rng() % n + 1;
ll k = rng() % 1000;
int slow = x, fast = x;
for (ll i = 0; i < k; i++) slow = f[slow];
for (int j = 0; j < LOG; j++) if (k >> j & 1) fast = up[j][fast];
if (slow != fast) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 500 tests passed";
}
all 500 tests passed
Memory: 60 · 200001 ints ≈ 48 MB. If the limit is tight, either use the tail-and-loop method (homework 2) or answer the queries offline.
Problem E3 · Lucky Number Machine
(Written for this course.)
x₀ is given and the next number is next(x) = (x² + c) mod m. Print the tail length μ and the loop length λ of x₀, x₁, x₂, …
- Input: m c x₀ (1 ≤ m ≤ 10^12, 0 ≤ c, x₀ < m).
- Memory limit: 4 MB.
This is a functional graph on the m values 0 … m − 1, but we never build it. x² can reach 10^24, beyond long long, so the multiplication uses __int128.
The obvious attempt: remember every number (MLE)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll m, c;
ll nxt(ll x) { return (ll)((__int128)x * x % m + c) % m; } // x * x can pass 10^18
int main() {
ll x;
cin >> m >> c >> x;
map<ll, ll> firstSeen; // number -> the step it appeared
for (ll i = 0; ; i++, x = nxt(x)) {
if (firstSeen.count(x)) {
cout << "tail " << firstSeen[x] << ", loop " << i - firstSeen[x] << "\n";
cout << "numbers stored: " << firstSeen.size() << "\n";
return 0;
}
firstSeen[x] = i;
}
}
tail 1, loop 6
numbers stored: 7
(3 → 0 → 1 → 2 → 5 → 6 → 7 → 0: tail 1, loop 6.)
999999999989 1 2
tail 542241, loop 598137
numbers stored: 1140378
1,140,378 map entries at roughly 50 bytes or more each (a red-black tree node plus the key and value) is over 50 MB: far beyond 4 MB.
Floyd's tortoise and hare
Two pointers start at x₀: slow moves 1 step, fast moves 2 steps, until they are equal.
- Once both are on the loop, fast gains one step per move, so they meet within λ moves. Say they meet after t moves: slow is at x_t, fast at x_2t, and x_t = x_2t, so the extra t steps are whole laps: t is a multiple of λ.
- Put slow back at x₀ and move both one step at a time. After μ steps slow is at x_μ, the start of the loop; fast is at x_(t+μ), which is μ plus a whole number of laps: also x_μ. The first meeting is at the loop's start, and the number of steps is μ.
- Walk one lap from there to count λ.
Time O(μ + λ), memory O(1).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll m, c;
ll nxt(ll x) { return (ll)((__int128)x * x % m + c) % m; } // x * x can pass 10^18
int main() {
ll x0;
cin >> m >> c >> x0;
ll slow = nxt(x0), fast = nxt(nxt(x0));
while (slow != fast) slow = nxt(slow), fast = nxt(nxt(fast)); // 1 step vs 2 steps
ll tail = 0;
slow = x0; // restart one runner at the gate
while (slow != fast) slow = nxt(slow), fast = nxt(fast), tail++; // same speed now
ll loop = 1;
fast = nxt(slow);
while (fast != slow) fast = nxt(fast), loop++; // one lap
cout << "tail " << tail << ", loop " << loop << "\n";
}
tail 1, loop 6
tail 542241, loop 598137
The same tail and loop as the map, with two variables. (Brent's algorithm is a variant that moves only one pointer and is often faster; Pollard's rho factorisation uses exactly this sequence x² + c.)
Complexity vs the constraints
| Method | Time | Memory | Verdict |
|---|---|---|---|
| E1: walk from every student | O(n²) | O(n) | TLE at n = 2 · 10^5 |
| E1: three states, reuse answers | O(n) | O(n) | accepted |
| E2: one jump at a time | O(k) per query | O(n) | TLE at k = 10^18 |
| E2: jump table, LOG = 60 | O((n + q) · 60) | 60 · n ints ≈ 48 MB | accepted |
| E2: tail + loop (homework 2) | O(n) per start (or O(n) total offline) | O(n) | accepted |
| E3: map of seen numbers | O((μ + λ) log) | O(μ + λ) ≈ 50+ MB | MLE |
| E3: Floyd | O(μ + λ) | O(1) | accepted |
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| walking from every vertex | Time Limit Exceeded |
the same tails walked again and again | reuse ans[f[i]] + 1 |
if (state[v]) instead of == 1 |
4 3 3 3 4 2 2 1 (expected … 5) |
a finished vertex is not on this walk | three states |
| LOG = 30 with k ≤ 10^18 | 3 6 2 (expected 3 6 4) |
high bits of k ignored | 2^LOG > max k |
int k |
reads fail, wrong answers | 10^18 does not fit in int | long long k |
x * x % m in long long, m ≤ 10^12 |
silently wrong numbers | x² overflows | (__int128)x * x % m |
| a map / set for every value seen | Memory Limit Exceeded | O(μ + λ) entries | Floyd, O(1) memory |
| recursive DFS down a 2 · 10^5 chain | Runtime Error on some judges | deep recursion, small stack | an explicit path and a loop |
| assuming the graph is connected | missing pieces | many pieces, each with its own loop | start a walk from every unvisited vertex |
Mini project
Write a FunctionalGraph class that, from f, computes for every vertex: onCycle, cycleId, cycleLen, posInCycle, tailLen (distance to the cycle) and entry (the first cycle vertex reached). Add jump(x, k) using a jump table only for the tail part (or, better, a k-th-ancestor query on the reversed trees) and k mod cycleLen on the cycle. Check it on random graphs against one-step-at-a-time simulation for k ≤ 1000, and on a chain, a single big cycle, all self-loops and a star into a 2-cycle.
Practice
These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17).
1. Count the loops in a functional graph. Input as in E1. Sample: the E1 sample.
Solution
A walk that stops at a state-1 vertex has found a new loop; one that stops at a state-2 vertex hasn't. Count the first kind. O(n).
#include <bits/stdc++.h>
using namespace std;
int n, f[200001], state[200001]; // 0 = not seen, 1 = on this walk, 2 = finished
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> f[i];
int loops = 0;
for (int s = 1; s <= n; s++) {
if (state[s]) continue;
vector<int> path;
int v = s;
while (state[v] == 0) {
state[v] = 1;
path.push_back(v);
v = f[v];
}
if (state[v] == 1) loops++; // came back to our own walk: a new loop
for (int u : path) state[u] = 2;
}
cout << loops << "\n";
}
2
2. One query (x, k), k ≤ 10^18, with no table. O(n) time and memory.
Solution
Walk from x until a vertex repeats, storing the path and pos[v]. The repeat vertex v gives μ = pos[v] and λ = path.size() − μ. If k < path.size() the answer is path[k], otherwise path[μ + (k − μ) mod λ]. Sample: the E1 graph, x = 1, k = 777777777777777777.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n, x;
ll k;
cin >> n;
vector<int> f(n + 1), pos(n + 1, -1);
for (int i = 1; i <= n; i++) cin >> f[i];
cin >> x >> k;
vector<int> path; // x, f(x), f(f(x)), ... until a repeat
int v = x;
while (pos[v] < 0) {
pos[v] = path.size();
path.push_back(v);
v = f[v];
}
ll tail = pos[v], loop = path.size() - tail;
if (k < (ll)path.size()) cout << path[k] << "\n";
else cout << path[tail + (k - tail) % loop] << "\n";
}
4
3. The sum of the gate numbers you land on in k jumps (k ≤ 10^9).
Solution
A second table sum[j][v] = sum of the gates landed on in 2^j jumps from v: sum[j][v] = sum[j−1][v] + sum[j−1][up[j−1][v]]. Combine the bits of k exactly like the gate itself. Queries: (8, 3) lands on 1, 2, 3 → 6; (6, 5) lands on 7, 6, 7, 6, 7 → 33; (1, 10^9).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int LOG = 30; // k <= 10^9 < 2^30
int n, q, up[LOG][200001];
ll sum[LOG][200001]; // sum of the gate numbers you land on in 2^j jumps
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> up[0][i], sum[0][i] = up[0][i];
for (int j = 1; j < LOG; j++)
for (int v = 1; v <= n; v++) {
int mid = up[j - 1][v];
up[j][v] = up[j - 1][mid];
sum[j][v] = sum[j - 1][v] + sum[j - 1][mid];
}
while (q--) {
int x;
ll k, total = 0;
cin >> x >> k;
for (int j = 0; j < LOG; j++)
if (k >> j & 1) total += sum[j][x], x = up[j][x];
cout << total << "\n";
}
}
6
33
2999999999
4. The fewest arrows to change so that every vertex is on a loop.
Solution
Every vertex lies on a loop exactly when f is a permutation, i.e. every vertex has in-degree exactly 1. The in-degrees add up to n, so the number of in-degree-0 vertices equals the total excess of the others. Each change can move one excess arrow onto an in-degree-0 vertex, and each in-degree-0 vertex needs at least one change: the answer is the number of vertices nobody points to. Sample: the E1 graph (5 and 8 have in-degree 0).
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> indeg(n + 1);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
indeg[x]++;
}
// every node on a loop <=> f is a permutation <=> every in-degree is exactly 1
int changes = 0;
for (int v = 1; v <= n; v++) if (indeg[v] == 0) changes++;
cout << changes << "\n";
}
2
Quick quiz
A walk has a tail of 4 positions (0 to 3), then a loop of 5 (positions 4 to 8). Where are you after 1000 steps?
positions 0 1 2 3 | 4 5 6 7 8 | 4 5 6 7 8 | …
A) position 4 · B) position 5 · C) position 6 · D) position 8
Answer
B. 4 steps reach position 4, the loop's start. 996 steps are left, and 996 mod 5 = 1, so one past the start: position 5. In general: position μ + (k − μ) mod λ for k ≥ μ.
Interview questions
- What is a functional graph? A directed graph where every vertex has out-degree exactly 1; the edges are a function f.
- Why does every walk end in a cycle? There are n vertices; after n + 1 steps some vertex repeats (pigeonhole), and from then on the walk repeats because f is deterministic.
- How many cycles can one connected component have? Exactly one. It has as many edges as vertices, so it is a tree plus one edge.
- How do you find all cycles in O(n)? Walk from every unvisited vertex with three states (unseen / on the current walk / finished); reaching a vertex on the current walk closes a new cycle.
- How do you find the k-th successor for huge k? Binary lifting (
up[j][v], 2^LOG > k), or tail length + cycle length + k mod λ. - Explain Floyd's cycle detection. Slow moves 1, fast moves 2; they meet inside the cycle after t moves with t a multiple of λ. Restart one pointer at the start; moving both by 1 they meet at the cycle start after μ steps. One more lap gives λ.
- Where else does this appear? Detecting a loop in a linked list, finding the duplicate in an array of n + 1 values in 1 … n, Pollard's rho, cycle of a pseudo-random generator, repeated states in simulations.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Functional graph (successor graph) | A directed graph where every vertex has exactly one outgoing edge | student i → f[i] |
| Out-degree / in-degree | Number of edges leaving / entering a vertex | out-degree 1 everywhere |
| Self-loop | An edge from a vertex to itself | f[i] = i |
| Walk | Following edges one after another, vertices may repeat | 8 → 1 → 2 → 3 → 4 → 2 |
| Cycle (loop) | A walk that returns to its start | 2 → 3 → 4 → 2 |
| Tail | The part of a walk before it enters the cycle | 8 → 1 |
| μ (mu) / λ (lambda) | The tail length / the cycle length of a walk | μ = 1, λ = 6 |
| ρ (rho) shape | A tail followed by a loop, drawn like the Greek letter | every walk here |
| Pigeonhole principle | n + 1 items in n boxes: some box has two | 9 hearings, 8 students |
| Component | A connected piece of the graph (ignoring directions) | {6, 7} |
| State 0 / 1 / 2 | Not seen / on the current walk / finished | three-state walk |
pos[v] |
Where v sits on the current path | loop length = path.size() − pos[v] |
| Jump table (binary lifting) | up[j][v] = vertex after 2^j steps |
LOG = 60 |
| LOG | Number of table levels; need 2^LOG > max k | 60 for 10^18 |
| Floyd's tortoise and hare | Cycle detection with a slow and a fast pointer | E3 |
__int128 |
A 128-bit integer type in g++ | (__int128)x * x % m |
| Integer overflow | A result too big for its type | x² with x ≈ 10^12 |
| Memory Limit Exceeded (MLE) | The program used more memory than allowed | the map in E3 |
| Permutation | A function where every value is hit exactly once | homework 4 |
| Stress test | Comparing a fast solution with a slow, surely-correct one on many random inputs | all 500 tests passed |
| O(n) | Linear time | the three-state walk |
| Time Limit Exceeded (TLE) | Too slow | walking from everyone |
| Wrong Answer (WA) | A wrong output | … 2 2 1 |
| Max flow | The most that can be sent through a network of capacities | next episode |
Summary
- A functional graph has one outgoing edge per vertex; every walk is a tail then a loop, and every component has exactly one loop.
- Find all loops in O(n) with three states; two states invent fake loops (
… 2 2 1). - On a loop the answer is the loop length; on a tail,
ans[i] = ans[f[i]] + 1, filled back to front. - k jumps: a jump table with 2^LOG > k (LOG = 60 for 10^18); LOG = 30 prints
2where4is right. - Floyd's tortoise and hare finds μ and λ with O(1) memory; multiply with
__int128when x² can overflow.
Solutions in C++, Java and Python
Problem E1 · Rumour Reach
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, f[200001], state[200001], pos[200001], ans[200001];
// state: 0 = not seen, 1 = on the current walk, 2 = finished
void solve() {
for (int s = 1; s <= n; s++) {
if (state[s]) continue;
vector<int> path;
int v = s;
while (state[v] == 0) { // walk until we meet something seen
state[v] = 1;
pos[v] = path.size();
path.push_back(v);
v = f[v];
}
if (state[v] == 1) { // back on our own walk: a new loop
int L = path.size() - pos[v];
for (int i = pos[v]; i < (int)path.size(); i++) ans[path[i]] = L, state[path[i]] = 2;
path.resize(pos[v]);
}
for (int i = (int)path.size() - 1; i >= 0; i--) { // the tail, back to front
int u = path[i];
ans[u] = ans[f[u]] + 1;
state[u] = 2;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> f[i];
solve();
for (int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
}
Java
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
int n = nextInt(in);
int[] f = new int[n + 1], state = new int[n + 1], pos = new int[n + 1], ans = new int[n + 1];
for (int i = 1; i <= n; i++) f[i] = nextInt(in);
int[] path = new int[n];
for (int s = 1; s <= n; s++) {
if (state[s] != 0) continue;
int len = 0, v = s;
while (state[v] == 0) { state[v] = 1; pos[v] = len; path[len++] = v; v = f[v]; }
if (state[v] == 1) { // a new loop
int L = len - pos[v];
for (int i = pos[v]; i < len; i++) { ans[path[i]] = L; state[path[i]] = 2; }
len = pos[v];
}
for (int i = len - 1; i >= 0; i--) { int u = path[i]; ans[u] = ans[f[u]] + 1; state[u] = 2; }
}
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= n; i++) sb.append(ans[i]).append(i == n ? "\n" : " ");
System.out.print(sb);
}
static int nextInt(DataInputStream in) throws IOException {
int r = 0, b = in.read();
while (b < '0') b = in.read();
while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
return r;
}
}
Python
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
f = [0] + [int(x) for x in data[1:n + 1]]
state = [0] * (n + 1) # 0 = not seen, 1 = on this walk, 2 = finished
pos = [0] * (n + 1)
ans = [0] * (n + 1)
for s in range(1, n + 1):
if state[s]:
continue
path = []
v = s
while state[v] == 0:
state[v] = 1
pos[v] = len(path)
path.append(v)
v = f[v]
if state[v] == 1: # back on our own walk: a new loop
L = len(path) - pos[v]
for u in path[pos[v]:]:
ans[u] = L
state[u] = 2
del path[pos[v]:]
for u in reversed(path): # the tail, back to front
ans[u] = ans[f[u]] + 1
state[u] = 2
print(" ".join(map(str, ans[1:])))
main()
4 3 3 3 4 2 2 5
Problem E2 · Teleport Gates
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int LOG = 60; // 2^60 > 10^18
int n, q, up[LOG][200001]; // up[j][v]: where 2^j jumps from v land
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> up[0][i];
for (int j = 1; j < LOG; j++)
for (int v = 1; v <= n; v++)
up[j][v] = up[j - 1][up[j - 1][v]]; // 2^j = 2^(j-1), twice
while (q--) {
int x;
ll k;
cin >> x >> k;
for (int j = 0; j < LOG; j++)
if (k >> j & 1) x = up[j][x]; // use the bits of k
cout << x << "\n";
}
}
Java
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tk = new StringTokenizer(br.readLine());
int n = Integer.parseInt(tk.nextToken()), q = Integer.parseInt(tk.nextToken());
final int LOG = 60; // 2^60 > 10^18
int[][] up = new int[LOG][n + 1];
tk = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) up[0][i] = Integer.parseInt(tk.nextToken());
for (int j = 1; j < LOG; j++)
for (int v = 1; v <= n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
tk = new StringTokenizer(br.readLine());
int x = Integer.parseInt(tk.nextToken());
long k = Long.parseLong(tk.nextToken());
for (int j = 0; j < LOG; j++) if ((k >> j & 1) == 1) x = up[j][x];
sb.append(x).append("\n");
}
System.out.print(sb);
}
}
Python (for the largest inputs, Python is slow: 60 levels × 2 · 10^5 is 1.2 · 10^7 list entries)
import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
LOG = 60 # 2^60 > 10^18
up = [[0] + [int(x) for x in data[2:n + 2]]]
for j in range(1, LOG):
prev = up[-1]
up.append([prev[prev[v]] for v in range(n + 1)])
out, p = [], n + 2
for _ in range(q):
x, k = int(data[p]), int(data[p + 1]); p += 2
j = 0
while k:
if k & 1:
x = up[j][x]
k >>= 1; j += 1
out.append(x)
print("\n".join(map(str, out)))
main()
3
6
4
Problem E3 · Lucky Number Machine
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll m, c;
ll nxt(ll x) { return (ll)((__int128)x * x % m + c) % m; } // x * x can pass 10^18
int main() {
ll x0;
cin >> m >> c >> x0;
ll slow = nxt(x0), fast = nxt(nxt(x0));
while (slow != fast) slow = nxt(slow), fast = nxt(nxt(fast)); // 1 step vs 2 steps
ll tail = 0;
slow = x0; // restart one runner at the gate
while (slow != fast) slow = nxt(slow), fast = nxt(fast), tail++; // same speed now
ll loop = 1;
fast = nxt(slow);
while (fast != slow) fast = nxt(fast), loop++; // one lap
cout << "tail " << tail << ", loop " << loop << "\n";
}
Java (BigInteger for the exact square)
import java.util.*;
import java.math.BigInteger;
public class Main {
static BigInteger M;
static long c, m;
static long nxt(long x) { // x * x can pass 2^63: multiply exactly
long sq = BigInteger.valueOf(x).multiply(BigInteger.valueOf(x)).mod(M).longValue();
return (sq + c) % m;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
m = sc.nextLong(); c = sc.nextLong(); long x0 = sc.nextLong();
M = BigInteger.valueOf(m);
long slow = nxt(x0), fast = nxt(nxt(x0));
while (slow != fast) { slow = nxt(slow); fast = nxt(nxt(fast)); } // 1 step vs 2 steps
long tail = 0;
slow = x0;
while (slow != fast) { slow = nxt(slow); fast = nxt(fast); tail++; } // same speed
long loop = 1;
fast = nxt(slow);
while (fast != slow) { fast = nxt(fast); loop++; }
System.out.println("tail " + tail + ", loop " + loop);
}
}
tail 542241, loop 598137
Python (integers never overflow)
import sys
m, c, x0 = map(int, sys.stdin.read().split())
nxt = lambda x: (x * x + c) % m # Python integers never overflow
slow, fast = nxt(x0), nxt(nxt(x0))
while slow != fast: # 1 step vs 2 steps
slow, fast = nxt(slow), nxt(nxt(fast))
tail, slow = 0, x0
while slow != fast: # same speed: meet at the loop start
slow, fast = nxt(slow), nxt(fast)
tail += 1
loop, fast = 1, nxt(slow)
while fast != slow:
fast = nxt(fast)
loop += 1
print(f"tail {tail}, loop {loop}")
tail 542241, loop 598137