(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.
Warning!
No Silver problem has required knowledge of the content presented in this module.
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 time and memory (not counting the graph itself).
Example - Cooperative Game
Focus Problem – read through this problem before continuing!
Hint 1
Hint 2
Solution
Solution
Example - Badge
Focus Problem – read through this problem before continuing!
It's easy to solve the above problem in time. We'll solve it in .
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=Falsedef dfs(x):global in_cycleif 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 sinceans[2] = -1
. Since we have reached2
for the second time, we know that2
is part of a cycle andans[2] = 2
. Similarly,ans[3] = 3
andans[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 thatans[1] = 2
, soans[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;int N;vector<int> adj, ans;vector<vector<int>> radj;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 inputfor(int i=1;i!=N;++i)
-th Successor
As described briefly in CPH 16.3, the -th successor of a certain node in a functional graph can be found in time using binary jumping, given time of preprocessing where is the maximum length of each jump. See the Platinum module for details.
Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
Silver | Easy | Show TagsFunctional Graph | |||
CSES | Easy | Show TagsFunctional Graph |
Additional problems involving functional graphs can be found in the Tree DP and Binary Jumping modules.