(Optional) Introduction to Functional Graphs

It's easy to solve the above problem in $O(N^2)$ time. We'll solve it in $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.

Solution - Badge

const int MN = 1e3+10;

int N, p[MN], f[MN];
bool v[MN], u[MN];
int dfs(int n)
{
    v[n]=u[n]=true;
    if(u[p[n]])//Cycle created
    {
        f[n]=n;//Nodes in cycle point to themselves

import java.io.*;
import java.util.*;

public class badge
{
    static InputReader in = new InputReader(System.in);
    static PrintWriter out = new PrintWriter(System.out);
    public static final int MN = 1010;
    public static int N;
    public static int[] p = new int[MN], f = new int[MN];

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 $O(N)$ time and $O(1)$ memory (not counting the graph itself).

Example - Cooperative Game

Solution

$K$-th Successor

As described briefly in CPH 16.3, can be found in $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.