# Introduction to Functional Graphs

Authors: Siyong Huang, Benjamin Qi, Andrew Wang

Contributors: Chuyang Wang, Ryan Chou

Directed graphs in which every vertex has exactly one outgoing edge.

## Introduction

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

Resources | ||||
---|---|---|---|---|

CPH | diagrams |

You can think of every connected component of a functional graph as a rooted tree with all edges directed toward the root 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

Focus Problem – try your best to solve this problem before continuing!

Hint 1

Hint 2

### Solution

Using **Floyd's Algorithm**, we can find some node on the cycle after
$2c\left\lceil \frac{t}{c}\right\rceil$ queries. Then we can find the first node
in the cycle after another $t$ queries.

C++

#include <iostream>#include <string>#include <vector>using std::cout;using std::endl;using std::pair;using std::vector;vector<int> move_result(const vector<int> &to_move) {

Java

import java.io.*;import java.util.*;public class CoopGame {static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));public static void main(String[] args) throws IOException {moveResult(new int[] {0, 1});int[] groups = moveResult(new int[] {1});while (groups[0] != groups[1]) {

Python

def move_result(to_move):"""Type annotations break the grader for some reason,so here's the signature of the function:move_result(to_move: Iterable[int]) -> list[int]"""print(f"next {' '.join(str(i) for i in to_move)}", flush=True)res = input().split()groups = [0 for _ in range(10)]

Do you see why this is equivalent to the code mentioned in CPH?

Python

a = succ(x)b = succ(succ(x))while a != b:a = succ(a)b = succ(succ(b))

Java

a = succ(x);b = succ(succ(x));while (a != b) {a = succ(a);b = succ(succ(b));}

C++

a = succ(x);b = succ(succ(x));while (a != b) {a = succ(a);b = succ(succ(b));}

$b$ corresponds to friend $1$ and $a$ corresponds to friend $0$.

Python

a = xwhile a != b:a = succ(a)b = succ(b)first = a

C++

a = x;while (a != b) {a = succ(a);b = succ(b);}first = a;

Java

a = x;while (a != b) {a = succ(a);b = succ(b);}first = a;

$a$ corresponds to friends $2\ldots 9$ and $b$ corresponds to friends $0$ and $1$.

## Example - Badge

Focus Problem – try your best to solve this problem before continuing!

While the constraints allow for a $\mathcal{O}(N^2)$ solution, it's possible to do this in just $\mathcal{O}(N)$!

### Solution 1

C++

#include <iostream>#include <vector>using std::cout;using std::endl;using std::vector;vector<int> p;vector<int> ans;bool in_cycle = false;

Java

import java.io.*;import java.util.*;public class Badge {public static int[] p;public static int[] ans;public static boolean in_cycle;public static void dfs(int n) {if (ans[n] != -2) {

Python

import syssys.setrecursionlimit(10**5)n = int(input())p = [int(i) - 1 for i in input().split()]assert n == len(p)def dfs(n: int) -> None:

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:

`dfs(0)`

->`dfs(1)`

->`dfs(2)`

->`dfs(3)`

->`dfs(4)`

->`dfs(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`

:`dfs(5)`

->`dfs(6)`

->`dfs(1)`

. We already know that`ans[1] = 2`

, so`ans[5] = ans[6] = 2`

as well.

### Solution 2

`floyd(x)`

generates answers for all vertices in the connected component containing
`x`

.
Note that this requires reverse adjacency lists.
In the code, these are stored in the variable `radj`

.

C++

#include <bits/stdc++.h>using namespace std;int n;vector<int> adj, ans;vector<vector<int>> radj;void fill_radj(int x) {for (auto &child : radj[x]) {/*

Java

import java.io.*;import java.util.*;public class Badge {static int[] adj;static int[] ans;/** For each node, we need a list to store its children; at nodes* combining the cycle with other part of the connected component, there* would be more than one outgoing arrow in the reversed adjacency list

Python

n = int(input())adj = [i - 1 for i in list(map(int, input().split()))]radj = [[] for _ in range(n)]ans = [-1] * ndef fill_radj(x: int) -> None:global ans"""

It's also possible to use `floyd(x)`

to generate answers for all vertices in the connected component
containing `x`

without using adjacency lists.

C++

#include <bits/stdc++.h>using namespace std;vector<int> res;vector<int> arr;/** fills up all vertices from curr to first_cycle,* whose answer has already been calculated*/

Java

import java.io.*;import java.util.*;public class Badge {static int[] ans;static int[] arr;public static void main(String[] args) throws IOException {BufferedReader x = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer(x.readLine());int n = Integer.parseInt(st.nextToken());

Python

def fill_up(curr: int, first_cycle: int):"""Fills up all vertices from curr to first_cycle,whose answer has already been calculated."""while curr != first_cycle:res[curr] = res[first_cycle]curr = arr[curr]

## Count Cycles

The following code counts the number of cycles in such a graph. The
"stack" contains nodes that can reach the current node. If the current node
points to a node `v`

on the stack (`on_stack[v]`

is true), then we know that a
cycle has been created. However, if the current node points to a node `v`

that
has been previously visited but is not on the stack, then we know that the
current chain of nodes points into a cycle that has already been considered.

### Warning!

The code below is untested. Use it at your own risk.

C++

bool visited[MAXN];bool on_stack[MAXN];int number_of_cycles = 0;int next_node[MAXN];void dfs(int n) {visited[n] = on_stack[n] = true;int u = next_node[n];if (on_stack[u]) {number_of_cycles++;

Java

import java.io.*;import java.util.*;public class CountCycles {static boolean[] visited = new boolean[MAXN];static boolean[] onStack = new boolean[MAXN];static int numberOfCycles = 0;static int[] nextNode = new int[MAXN];public static void main(String[] args) throws IOException {

Python

vis = [False] * MAXNon_stack = [False] * MAXNnext_node = [0] * MAXNnumber_of_cycles = 0def dfs(n: int) -> None:global number_of_cyclesvis[n] = on_stack[n] = True

## $K$-th Successor

As described briefly in CPH 16.3, the $k$-th successor of a certain node in a functional graph can be found in $\mathcal{O}(\log k)$ time
using **binary jumping**, given $\mathcal{O}(n \log u)$ time of preprocessing where $u$ is the maximum length of each jump. See the Platinum module for details.

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Silver | Easy | ## Show TagsFunctional Graph | |||

CSES | Easy | ## Show TagsFunctional Graph | |||

Silver | Normal | ## Show TagsSCC | |||

Old Silver | Normal | ## Show TagsFunctional Graph | |||

IOI | Very Hard | ## Show TagsFunctional Graph |

## Quiz

What's a functional graph (successor graph)?

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

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!