Introduction Floyd's Algorithm Example - Cooperative Game Solution Example - Badge Solution 1 Solution 2 Count Cycles

K

Not Frequent

0/7

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.

Edit This Page

Prerequisites

Silver - Introduction to Tree Algorithms

Introduction Floyd's Algorithm Example - Cooperative Game Solution Example - Badge Solution 1 Solution 2 Count Cycles

K

-th Successor Problems Quiz

Introduction

In a functional graph, each node has exactly one out-edge. This is also commonly referred to as a successor graph.

Resources
	CPH	16.3 - Successor Graphs	diagrams

You can think of every connected component of a functional graph as a rooted tree with all edges directed toward the root 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	16.4 - Cycle Detection
	Medium	The Tortoise and the Hare (Floyd's Algorithm)
	CP2	5.7 - Cycle-Finding
	VisuAlgo	Floyd's Algorithm Visualization

Example - Cooperative Game

Cooperative Game

CF - Hard

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 class CoopGame {
	static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

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

Example - Badge

Div 2 B - Badge

CF - Very Easy

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.

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[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: dfs(5) -> dfs(6) -> dfs(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. 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;

int n;
vector<int> adj, ans;
vector<vector<int>> radj;

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

	"""

It's also possible to use floyd(x) to generate answers for all vertices in the connected component containing x without using adjacency lists.

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> res;
vector<int> arr;

/*
 * fills up all vertices from curr to first_cycle,
 * whose answer has already been calculated
 */

Java

import java.io.*;
import java.util.*;

public class Badge {
	static int[] ans;
	static int[] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader x = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(x.readLine());
		int n = Integer.parseInt(st.nextToken());

Python

def fill_up(curr: int, first_cycle: int):
	"""
	Fills up all vertices from curr to first_cycle,
	whose answer has already been calculated.
	"""
	while curr != first_cycle:
		res[curr] = res[first_cycle]
		curr = arr[curr]

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] * MAXN
on_stack = [False] * MAXN
next_node = [0] * MAXN
number_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

Source	Problem Name	Difficulty	Tags
Silver	The Bovine Shuffle	Easy	Show Tags Functional Graph
CSES	Planets Cycles	Easy	Show Tags Functional Graph
Silver	Visits	Normal	Show Tags SCC
Old Silver	Luxury River Cruise	Normal	Show Tags Functional Graph
IOI	Tropical Garden	Very Hard	Show Tags Functional Graph

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.

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!

Join Forum

Table of Contents

Introduction to Functional Graphs

Prerequisites

Table of Contents

Introduction

Floyd's Algorithm

Example - Cooperative Game

Solution

Example - Badge

Solution 1

Solution 2

Count Cycles

Warning!

$K$ -th Successor

Problems

Quiz

Module Progress:

Join the USACO Forum!

Table of Contents

Introduction to Functional Graphs

Prerequisites

Table of Contents

Introduction

Floyd's Algorithm

Example - Cooperative Game

Solution

Example - Badge

Solution 1

Solution 2

Count Cycles

Warning!

KKK-th Successor

Problems

Quiz

Module Progress:Not Started

Join the USACO Forum!

$K$ -th Successor

Module Progress: