PrevNext

You're not signed in!

Sign in to save your progress and sync your settings across devices.

Rare
 0/5

(Optional) Introduction to Functional Graphs

Authors: Siyong Huang, Benjamin Qi, Andrew Wang

Directed graphs in which every vertex has exactly one outgoing edge.

Focus Problem – read through this problem before continuing!


It's easy to solve the above problem in O(N2)O(N^2) time. We'll solve it in O(N)O(N).

Introduction

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

Resources
CPHdiagrams

You can think of every connected component of a functional graph as a rooted tree plus an additional edge going out of the root.

Solution - Badge

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

C++

1const int MN = 1e3+10;
2
3int N, p[MN], f[MN];
4bool v[MN], u[MN];
5int dfs(int n)
6{
7 v[n]=u[n]=true;
8 if(u[p[n]])//Cycle created
9 {
10 f[n]=n;//Nodes in cycle point to themselves

Java

1import java.io.*;
2import java.util.*;
3
4public class badge
5{
6 static InputReader in = new InputReader(System.in);
7 static PrintWriter out = new PrintWriter(System.out);
8 public static final int MN = 1010;
9 public static int N;
10 public static int[] p = new int[MN], f = new int[MN];

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)O(N) time and O(1)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

KK-th Successor

As described briefly in CPH 16.3, can be found in O(logK)O(\log K) time using binary jumping. See the Platinum module for details.

Problems

StatusSourceProblem NameDifficultyTagsSolution
SilverEasy
Show Tags

Func Graph

External Sol
CSESNormal
Show Tags

Func Graph

View Solution
SilverNormal
Show Tags

Permutation

External Sol

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

Module Progress:

Give Us Feedback on (Optional) Introduction to Functional Graphs!

PrevNext