Rare
0/5

# (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 – read through this problem before continuing!

Hint 1

Hint 2

### Solution

Solution

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

### 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=False
def dfs(x):	global in_cycle	if 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;
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 input		for(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

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

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!