Chapter 5.3: Functional Graphs

English translation of this chapter is coming soon. Please refer to the Chinese version for now.

Content Outline

5.3.1 What is a Functional Graph?

• Definition
• Structural Feature: Rho Shape
• Key Conclusion: Each Component Has Exactly One Cycle

5.3.2 Finding Cycles (Floyd's Cycle Detection / Coloring Method)

• Method 1: Coloring Method (Recommended for USACO)
• Method 2: Floyd's Cycle Detection (Fast and Slow Pointers)

5.3.3 Walk k Steps Problem (Binary Lifting Acceleration)

• Naive Approach: O(k)
• Binary Lifting: Preprocessing jump[v][j]

5.3.4 Typical USACO Silver Problem Types

• Type 1: Connectivity in Functional Graphs
• Type 2: Distribution After Walking Exactly k Steps

5.3.5 Complete Example: Cow Jumping (USACO Silver Style)

Common Mistakes

Exercises

1. Find All Cycles
2. Walk k Steps
3. Nearest Common Successor (LCA on Functional Graphs)