# (Optional) Introduction to Functional Graphs

Authors: Siyong Huang, Benjamin Qi, Andrew Wang

### Prerequisites

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

Focus Problem – read through 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)$.

## 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).

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

CPH | |||

Medium |

### Example - Cooperative Game

Focus Problem – read through this problem before continuing!

Hint 1

Hint 2

### Solution

Solution

## Solution - Badge

### Solution 1

C++

int N;vi P,ans;bool in_cycle;void gen(int x) {if (ans[x] != -2) {if (ans[x] == -1) ans[x] = x, in_cycle = 1; // found a cycle!return;}ans[x] = -1; gen(P[x]);

Java

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

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`

).

C++

int N;vi P,ans;V<vi> radj;void fill_radj(int x) {trav(t,radj[x]) if (ans[t] == -1) {ans[t] = ans[x];fill_radj(t);}}

## 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, can be found in $\mathcal{O}(\log K)$ time using **binary jumping**. See the Platinum module for details.

## Problems

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

Silver | Easy | ## Show TagsFunc Graph | External Sol | |||

CSES | Easy | ## Show TagsFunc Graph | View Solution | |||

Silver | Normal | ## Show TagsPermutation | External Sol |

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!

## Give Us Feedback on (Optional) Introduction to Functional Graphs!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.