PrevNext
Not Frequent
 0/5

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 O(N)\mathcal{O}(N) time and O(1)\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 2ctc2c\left\lceil \frac{t}{c}\right\rceil queries. Then we can find the first node in the cycle after another tt queries.

Python

import sys
pos = [0] * 10
def qry(x: list) -> None:
print("next", end=" ")
for i in x:
print(i, end=" ")

C++

#include <cstdio>
#include <vector>
void out(const std::vector<int> &x) {
printf("next");
for (auto a : x) printf(" %d", a);
printf("\n");
fflush(stdout);
}
int N, g[20];

Java

import java.io.*;
import java.util.*;
public class Cooperative {
public static int g[];
public static BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
public static void out(int arr[]) {
System.out.print("next");
for (int a : arr) { System.out.print(" " + a); }

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

C++

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));
}

bb corresponds to friend 11 and aa corresponds to friend 00.

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;

aa corresponds to friends 292\ldots 9 and bb corresponds to friends 00 and 11.

Example - Badge

Focus Problem – try your best to solve this problem before continuing!


It's easy to solve the above problem in O(N2)\mathcal{O}(N^2) time. We'll solve it in O(N)\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;
public static void dfs(int n) {

Python

N = int(input())
p = list(map(int, input().split()))
ans = [-1] * N
in_cycle = False
def dfs(x):
global in_cycle
if ans[x] != -1:
if ans[x] == -2: # found a cycle!

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

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

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 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]) number_of_cycles++;
else if (!visited[u]) dfs(u);

Java

// source: Mayank Kumar
import 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)

Python

import sys
# may need for large inputs
sys.setrecursionlimit(1000000)
vis = [0] * MAXN
on_stack = [0] * MAXN
next_node = [0] * MAXN
num_of_cycles = 0

KK-th Successor

As described briefly in CPH 16.3, the kk-th successor of a certain node in a functional graph can be found in O(logk)\mathcal{O}(\log k) time using binary jumping, given O(nlogu)\mathcal{O}(n \log u) time of preprocessing where uu 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.

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!

PrevNext