### You're not signed in!

Sign in to save your progress and sync your settings across devices.

# (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 $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**.

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.

### Solution - Badge

### This section is not complete.

C++

1const int MN = 1e3+10;23int N, p[MN], f[MN];4bool v[MN], u[MN];5int dfs(int n)6{7 v[n]=u[n]=true;8 if(u[p[n]])//Cycle created9 {10 f[n]=n;//Nodes in cycle point to themselves

Java

1import java.io.*;2import java.util.*;34public class badge5{6 static InputReader in = new InputReader(System.in);7 static PrintWriter out = new PrintWriter(System.out);8 public static final int MN = 1010;9 public static int N;10 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).

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

CPH | |||

Medium |

### Example - Cooperative Game

Focus Problem – read through this problem before continuing!

Hint 1

Hint 2

### Solution

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

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

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

CSES | Normal | ## 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.