SyntaxPilot
Courses/Competitive Programming/Lesson 57
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 57 of 90

Functional graphs and cycle finding

queued

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.

  1. 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 λ.
  2. 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 μ.
  3. 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

  1. What is a functional graph? A directed graph where every vertex has out-degree exactly 1; the edges are a function f.
  2. 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.
  3. 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.
  4. 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.
  5. 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 λ.
  6. 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 λ.
  7. 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 2 where 4 is right.
  • Floyd's tortoise and hare finds μ and λ with O(1) memory; multiply with __int128 when 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