# (Optional) Introduction to Functional Graphs

Authors: Siyong Huang, Benjamin Qi, Andrew Wang

Contributor: Chuyang Wang

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 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

Solution

## Example - Badge

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

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

### Solution 1

C++

#include <bits/stdc++.h>using namespace std;int N;vector<int> P,ans;bool in_cycle;void gen(int x) {if (ans[x] != -2) {

Java

import java.io.*;import java.util.*;public class badge{static BufferedReader reader;static PrintWriter writer;public static final int MN = 1010;public static int[] p, ans;public static boolean in_cycle;

Python

N=int(input())p=list(map(int, input().split()))ans=[-1]*Nin_cycle=Falsedef dfs(x):global in_cycleif ans[x] != -1:if ans[x] == -2: # found a cycle!in_cycle = True

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

`floyd(x)`

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

. Requires reverse adjacency lists (`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.util.*;import java.io.*;public class Badge {static Integer[] adj, 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*/

## Count Cycles

The following sample 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.

C++

//UNTESTED//Each node points to next_node[node]bool visited[MAXN], on_stack[MAXN];int number_of_cycles = 0, next_node[MAXN];void dfs(int n){visited[n] = on_stack[n] = true;int u = next_node[n];if(on_stack[u])

Java

//source: Mayank Kumarimport java.io.*;import java.util.*;public class badge2{static boolean[] visited=new boolean[MAXN],onStack=new boolean[MAXN];static int numberOfCycles=0;static int[] nextNode=new int[MAXN];public static void main(String[] args) throws IOException{//Take in inputfor(int i=1;i!=N;++i)

## $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 |

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!