Functional Graphs
What if every node has exactly one outgoing edge? These functional graphs have special structure.
Lessons
1. Intro
(The special constraint)
2. Function Notation
(Successor as a function)
3. The Rho Shape
(Why cycles always appear)
4. Example Graph
(Visualizing the structure)
5. Why This Matters
(The power of predictability)
6. Floyd's Algorithm
(Tortoise and hare)
7. Floyd's Implementation
(The detection phase)
8. Finding Cycle Start
(The meeting point trick)
9. Why Floyd Works
(The distance proof)
10. Cycle Length
(Measuring the loop)
11. Problem - Linked List Cycle II
(LeetCode 142)
12. Core Idea - Two-Phase Approach
(Detection then location)
13. Core Idea - Null Pointer Check
(Handling no cycle case)
14. Linked List Cycle II - Implementation
(Floyd's algorithm in code)
15. Linked List Cycle II - Walkthrough
(Example execution)
16. Linked List Cycle II - Lessons
(summary)
17. Binary Lifting for Successors
(Jumping in powers of 2)
18. Preprocessing Table
(Computing jump pointers)
19. Query Processing
(Decomposing k into powers)
20. Problem - Planets Queries I
(CSES 1750)
21. Core Idea - Preprocessing Once
(Amortizing the cost)
22. Core Idea - Binary Representation
(Why powers of 2 work)
23. Planets Queries I - Implementation
(Binary lifting in code)
24. Planets Queries I - Walkthrough
(Example execution)
25. Planets Queries I - Lessons
(summary)
26. Quiz: Functional Graph Distances
Knowledge check
27. Tail vs Cycle Position
(Two regions)
28. Precomputing Cycle Info
(One-pass detection)
29. Distance Query Cases
(Four scenarios)
30. Problem - Planets Queries II
(CSES 1160)
31. Core Idea - Cycle Membership
(Marking the loop)
32. Core Idea - Distance to Cycle
(Tail length computation)
33. Core Idea - Cycle Position Index
(Tracking location in loop)
34. Planets Queries II - Walkthrough
(Example execution)
35. Planets Queries II - Lessons
(summary)
36. Problem - Planet Cycles
(CSES 1751)
37. Core Idea - DFS with Memoization
Computing all distances at ...
38. Core Idea - Color-Based Detection
(Tracking DFS state)
39. Planet Cycles - Walkthrough
(Example execution)
40. Planet Cycles - Lessons
(summary)
41. Permutation Cycles
(Application to permutations)
42. Cycle Decomposition
(Breaking into components)
43. Application - Sorting with Swaps
(Minimum swaps to sort)
44. Application - Josephus Problem
(Elimination sequences)
45. Space Improvement
(Reducing memory usage)
46. Common Mistakes
(What goes wrong)
47. Section Recap
(What you learned)