Not Frequent
0/5

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

Official Tutorial

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 static void main(String[] args) throws IOException {		moveResult(new int[] {0, 1});		int[] groups = moveResult(new int[] {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$.

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 sys
sys.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 = -1. Since we have reached 2 for the second time, we know that 2 is part of a cycle and ans = 2. Similarly, ans = 3 and ans = 4 since they are part of the cycle. On the other hand, ans = ans = 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 = 2, so ans = ans = 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;
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] * n

def fill_radj(x: int) -> None:	global ans
"""

## 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 =  * MAXNnumber_of_cycles = 0

def dfs(n: int) -> None:	global number_of_cycles	vis[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

StatusSourceProblem NameDifficultyTags
SilverEasy
Show TagsFunctional Graph
CSESEasy
Show TagsFunctional Graph
SilverNormal
Show TagsSCC

## Quiz

What's a functional graph (successor graph)?

Question 1 of 4

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

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