(Optional) Introduction to Functional Graphs

It's easy to solve the above problem in $\mathcal{O}(N^2)$ time. We'll solve it in $\mathcal{O}(N)$.

Introduction

In a functional graph, each node has exactly one out-edge. This is also commonly referred to as a successor graph.

You can think of every connected component of a functional graph as a rooted tree plus an additional edge going out of the root.

Floyd's Algorithm

Floyd's Algorithm, also commonly referred to as the Tortoise and Hare Algorithm, is capable of detecting cycles in a functional graph in $\mathcal{O}(N)$ time and $\mathcal{O}(1)$ memory (not counting the graph itself).

Example - Cooperative Game

Solution

Solution - Badge

Solution 1

1int N;
2vi P,ans;
3bool in_cycle;
4
5void gen(int x) {
6    if (ans[x] != -2) {
7        if (ans[x] == -1) ans[x] = x, in_cycle = 1; // found a cycle!
8        return;
9    }
10    ans[x] = -1; gen(P[x]);

This code generates the answer independently for each connected component. Note that it uses 0-indexing, not 1-indexing.

Try simulating the algorithm on the following directed graph in CSAcademy's Graph Editor.

0 1
1 2
2 3
3 4
4 2
5 6
6 1

• On the first step, we make the following recursive calls: gen(0) -> gen(1) -> gen(2) -> gen(3) -> gen(4) -> gen(2), at which point we stop since ans[2] = -1. Since we have reached 2 for the second time, we know that 2 is part of a cycle and ans[2] = 2. Similarly, ans[3] = 3 and ans[4] = 4 since they are part of the cycle. On the other hand, ans[0] = ans[1] = 2 since neither of them are part of the cycle.

• Later, we make the following recursive calls when we start at vertex 5: gen(5) -> gen(6) -> gen(1). We already know that ans[1] = 2, so ans[5] = ans[6] = 2 as well.

Solution 2

go(x) generates answers for all vertices in the connected component containing x. Requires reverse adjacency lists (radj).

1int N;
2vi P,ans;
3V<vi> radj;
4
5void fill_radj(int x) {
6    trav(t,radj[x]) if (ans[t] == -1) {
7        ans[t] = ans[x];
8        fill_radj(t);
9    }
10}

$K$-th Successor

As described briefly in CPH 16.3, can be found in $\mathcal{O}(\log K)$ time using binary jumping. See the Platinum module for details.

Problems

Additional problems involving functional graphs can be found in the Tree DP and Binary Jumping modules.