Loading repovive.com/roadmaps/graph-theory
Roadmaps
Graph Theory
Binary Lifting
Problemset
Discussion
AI Helper
Graph Fundamentals
0/41
1
Intro
2
What is a Graph?
3
Real World Example - The Map
4
Real World Example - Social Networks
5
Why Graphs Matter
6
Vocabulary - The Vertex
7
Vocabulary - The Edge
8
Quiz: Vertices and Edges
9
Formal Notation
10
Types of Graphs - Undirected
11
Types of Graphs - Directed
12
Classify the Graph
13
The Representation Problem
14
Quiz: Directed vs Undirected
15
Method 1 - The Adjacency Matrix
16
Matrix - Visual Example
17
Matrix - The Problem
18
Method 2 - The Adjacency List
19
Adjacency List - Visual Example
20
Adjacency List - Efficiency
21
Quiz: Adjacency Matrix vs List
22
Implementing in C++
23
Explaining the Syntax
24
Adding Directed Edges
25
Adding Undirected Edges
26
Graph Degrees
27
Directed Degrees
28
Quiz: Graph Degrees
29
Problem Time - Town Judge
30
Town Judge - The Story
31
Town Judge - Graph Translation
32
Town Judge - The Algorithm
33
Town Judge - Implementation
34
Problem Time - Star Graph
35
Star Graph - Method 1
36
Star Graph - Method 2
37
Star Graph - The Trick
38
Star Graph - Implementation
39
Quiz: Graph Representations in Code
40
Cities and Roads
41
Section Recap
Depth First Search (DFS)
0/41
1
Intro
2
The Visited Array
3
The DFS Logic Flow
4
The Code Template
5
How to Call It
6
Visualizing the Trace
7
Quiz: DFS Traversal Order
8
Time Complexity of DFS
9
Space Complexity of DFS
10
Quiz: DFS Complexity
11
LeetCode 133 Clone Graph - Problem Statement
12
LeetCode 133 Clone Graph - Strategy
13
LeetCode 133 Clone Graph - Why Depth First
14
LeetCode 133 Clone Graph - Handling Cycles
15
LeetCode 133 Clone Graph - Core Idea
16
LeetCode 133 Clone Graph - Algorithm
17
LeetCode 133 Clone Graph - Recursion
18
LeetCode 133 Clone Graph - Implementation
19
LeetCode 133 Clone Graph - Lessons
20
Quiz: Cycle Handling in DFS
21
LeetCode 841 Keys and Rooms - Problem Statement
22
LeetCode 841 Keys and Rooms - Mapping
23
LeetCode 841 Keys and Rooms - Solution
24
LeetCode 841 Keys and Rooms - Implementation
25
Connected Components
26
Counting Components - The Idea
27
Counting Components - Algorithm
28
Quiz: Connected Components
29
LeetCode 547 Number of Provinces - Problem Statement
30
LeetCode 547 Number of Provinces - Input
31
LeetCode 547 Number of Provinces - Implementation
32
DFS on Trees
33
Avoiding Cycles in Trees
34
Carrying State in DFS
35
Quiz: DFS on Trees
36
Codeforces 580C Kefa and Park - Problem Statement
37
Codeforces 580C Kefa and Park - State
38
Codeforces 580C Kefa and Park - Logic
39
Codeforces 580C Kefa and Park - Implementation
40
Quiz: DFS State Tracking
41
Section Recap
Breadth First Search (BFS)
0/40
1
Intro
2
The Ripple Effect
3
The Data Structure
4
The BFS Strategy
5
The BFS Algorithm Step 1
6
The BFS Algorithm Step 2
7
The BFS Algorithm Step 3
8
Why does this find Shortest Path?
9
Quiz: BFS Shortest Path Guarantee
10
Tracking Distances
11
Implicit Graphs
12
Complexity of BFS
13
Quiz: BFS Complexity
14
DFS vs BFS Summary
15
BFS Variants Summary
16
LeetCode 1091 Shortest Path in Binary Matrix - Problem Statement
17
LeetCode 1091 Shortest Path in Binary Matrix - Grid BFS
18
LeetCode 1091 Shortest Path in Binary Matrix - Implementation Details
19
LeetCode 1091 Shortest Path in Binary Matrix - Direction Arrays
20
CSES 1667 Message Route - Problem Statement
21
CSES 1667 Message Route - Path Reconstruction Idea
22
CSES 1667 Message Route - Path Reconstruction Algorithm
23
CSES 1667 Message Route - Implementation
24
Quiz: BFS Path Reconstruction
25
LeetCode 127 Word Ladder - Problem Statement
26
LeetCode 127 Word Ladder - Finding Neighbors
27
LeetCode 127 Word Ladder - Implementation
28
LeetCode 994 Rotting Oranges - Problem Statement
29
LeetCode 994 Rotting Oranges - Core Idea
30
LeetCode 994 Rotting Oranges - Algorithm
31
LeetCode 994 Rotting Oranges - Implementation
32
LeetCode 994 Rotting Oranges - Lessons
33
Quiz: Multi-Source BFS
34
LeetCode 542 01 Matrix - Problem Statement
35
LeetCode 542 01 Matrix - Core Idea
36
LeetCode 542 01 Matrix - Algorithm
37
LeetCode 542 01 Matrix - Implementation
38
LeetCode 542 01 Matrix - Lessons
39
Quiz: BFS vs DFS for Shortest Path
40
Section Recap
Flood Fill & Grid Graphs
0/32
1
Intro
2
The Paint Bucket
3
Counting Islands
4
Dependencies and Cycles
5
Cycle Detection - The Logic
6
The Three Colors
7
Cycle Detection - Visualizing
8
Quiz: Grid Graph Traversal
9
Not Every Grid Needs Traversal
10
Quiz: Cycle Detection in Directed Graphs
11
LeetCode 733 Flood Fill - Problem Statement
12
LeetCode 733 Flood Fill - Strategy
13
LeetCode 733 Flood Fill - Why It Works
14
LeetCode 733 Flood Fill - Implementation
15
LeetCode 200 Number of Islands - Problem Statement
16
LeetCode 200 Number of Islands - Core Idea
17
LeetCode 200 Number of Islands - Visualization
18
LeetCode 200 Number of Islands - Implementation
19
Quiz: Island Counting Logic
20
LeetCode 463 Island Perimeter - Problem Statement
21
LeetCode 463 Island Perimeter - Core Idea
22
LeetCode 463 Island Perimeter - Algorithm
23
LeetCode 463 Island Perimeter - Implementation
24
LeetCode 463 Island Perimeter - Lessons
25
Quiz: Perimeter vs Area
26
LeetCode 695 Max Area of Island - Problem Statement
27
LeetCode 695 Max Area of Island - Core Idea
28
LeetCode 695 Max Area of Island - Algorithm
29
LeetCode 695 Max Area of Island - Implementation
30
LeetCode 695 Max Area of Island - Lessons
31
Quiz: Flood Fill Boundaries
32
Section Recap
Bipartite Graphs
0/48
1
Intro
2
What Is a Bipartite Graph?
3
Vocabulary - 2-Coloring
4
Vocabulary - Partition
5
Real World Examples
6
The Odd Cycle Rule
7
Visualizing the Odd Cycle
8
Quiz: Bipartite Basics
9
Detection Strategy
10
BFS for Detection
11
DFS for Detection
12
Disconnected Graphs
13
DFS Implementation
14
BFS vs DFS Trade-offs
15
Common Mistakes
16
Time and Space Complexity
17
LeetCode 785 Is Graph Bipartite? - Problem Statement
18
LeetCode 785 Is Graph Bipartite? - Input Format
19
LeetCode 785 Is Graph Bipartite? - The Color Array
20
LeetCode 785 Is Graph Bipartite? - Detecting Conflicts
21
LeetCode 785 Is Graph Bipartite? - The Outer Loop
22
LeetCode 785 Is Graph Bipartite? - Algorithm
23
LeetCode 785 Is Graph Bipartite? - Implementation
24
LeetCode 785 Is Graph Bipartite? - Walkthrough
25
LeetCode 785 Is Graph Bipartite? - Conflict Example
26
LeetCode 785 Is Graph Bipartite? - Lessons
27
Quiz: Detection Logic
28
LeetCode 886 Possible Bipartition - Problem Statement
29
LeetCode 886 Possible Bipartition - Story
30
LeetCode 886 Possible Bipartition - Recognizing the Pattern
31
LeetCode 886 Possible Bipartition - Building the Graph
32
LeetCode 886 Possible Bipartition - Index Handling
33
LeetCode 886 Possible Bipartition - Algorithm
34
LeetCode 886 Possible Bipartition - Implementation
35
LeetCode 886 Possible Bipartition - Walkthrough
36
LeetCode 886 Possible Bipartition - Lessons
37
Quiz: Problem Recognition
38
CSES 1668 Building Teams - Problem Statement
39
CSES 1668 Building Teams - Input Format
40
CSES 1668 Building Teams - Output Format
41
CSES 1668 Building Teams - Core Idea
42
CSES 1668 Building Teams - Algorithm
43
CSES 1668 Building Teams - Implementation
44
CSES 1668 Building Teams - Walkthrough
45
CSES 1668 Building Teams - Lessons
46
Quiz: Edge Cases
47
What's Next
48
Section Recap
Tree Fundamentals
0/44
1
Intro
2
Visualizing a Tree
3
Rooting the Tree
4
Moving in a Tree
5
Tree DFS Template
6
Concept - Depth vs Height
7
Quiz: Tree Properties
8
LeetCode 104 Maximum Depth of Binary Tree - Problem Statement
9
LeetCode 104 Maximum Depth of Binary Tree - Strategy
10
LeetCode 104 Maximum Depth of Binary Tree - Implementation
11
Concept - Tree Dynamic Programming
12
CSES 1674 Subordinates - Problem Statement
13
CSES 1674 Subordinates - Strategy
14
CSES 1674 Subordinates - Implementation
15
Quiz: Subtree Size Computation
16
Concept - Tree Diameter
17
LeetCode 543 Diameter of Binary Tree - Problem Statement
18
LeetCode 543 Diameter of Binary Tree - Strategy
19
LeetCode 543 Diameter of Binary Tree - Implementation Details
20
LeetCode 543 Diameter of Binary Tree - Takeaway
21
Quiz: Tree Diameter
22
Concept - General Tree Diameter
23
CSES 1131 Tree Diameter - Problem Statement
24
CSES 1131 Tree Diameter - Double BFS Algorithm
25
CSES 1131 Tree Diameter - Why Double BFS Works
26
CSES 1131 Tree Diameter - Two Approaches Compared
27
Concept - Tree Centers
28
LeetCode 310 Minimum Height Trees - Problem Statement
29
LeetCode 310 Minimum Height Trees - Strategy
30
LeetCode 310 Minimum Height Trees - Implementation
31
Quiz: Tree Centers
32
LeetCode 100 Same Tree - Problem Statement
33
LeetCode 100 Same Tree - Strategy
34
LeetCode 100 Same Tree - Algorithm
35
LeetCode 100 Same Tree - Implementation
36
LeetCode 100 Same Tree - Lessons
37
Quiz: Tree Comparison
38
LeetCode 226 Invert Binary Tree - Problem Statement
39
LeetCode 226 Invert Binary Tree - Strategy
40
LeetCode 226 Invert Binary Tree - Algorithm
41
LeetCode 226 Invert Binary Tree - Implementation
42
LeetCode 226 Invert Binary Tree - Lessons
43
Quiz: Tree Inversion
44
Section Recap
Tree Diameter & Center
0/45
1
Intro
2
What is Tree Diameter
3
Why Diameter Matters
4
The Naive Approach
5
The Two-BFS Trick
6
Why Two-BFS Works
7
Two-BFS Implementation
8
Quiz: Two-BFS Method
9
CSES 1131 Tree Diameter - Problem Statement
10
CSES 1131 Tree Diameter - Core Idea
11
CSES 1131 Tree Diameter - Algorithm
12
CSES 1131 Tree Diameter - Implementation
13
CSES 1131 Tree Diameter - Walkthrough
14
CSES 1131 Tree Diameter - Lessons
15
The DP Approach
16
DP Method - How It Works
17
DP Method - Implementation
18
Two-BFS vs DP
19
Quiz: Diameter Methods
20
LeetCode 543 Diameter of Binary Tree - Problem Statement
21
LeetCode 543 Diameter of Binary Tree - Core Idea
22
LeetCode 543 Diameter of Binary Tree - Algorithm
23
LeetCode 543 Diameter of Binary Tree - Implementation
24
LeetCode 543 Diameter of Binary Tree - Lessons
25
Tree Center
26
Finding the Center
27
Center via Diameter
28
Tree Eccentricity and Radius
29
Quiz: Tree Center
30
CSES 1132 Tree Distances I - Problem Statement
31
CSES 1132 Tree Distances I - Core Idea
32
CSES 1132 Tree Distances I - Algorithm
33
CSES 1132 Tree Distances I - Implementation
34
CSES 1132 Tree Distances I - Walkthrough
35
CSES 1132 Tree Distances I - Lessons
36
CSES 1133 Tree Distances II - Problem Statement
37
CSES 1133 Tree Distances II - Core Idea
38
CSES 1133 Tree Distances II - Algorithm
39
CSES 1133 Tree Distances II - Implementation
40
CSES 1133 Tree Distances II - Walkthrough
41
CSES 1133 Tree Distances II - Lessons
42
Quiz: Sum of Distances
43
Comparing the Problems
44
Common Mistakes
45
Section Recap
Subtree DP
0/44
1
Intro
2
Trees as Recursive Structures
3
What is Subtree DP
4
DFS for Tree DP
5
Example: Count Subtree Sizes
6
Quiz: Basic Tree DP
7
State Definition on Trees
8
Aggregating Child Values
9
Time Complexity of Tree DP
10
Rooted vs Unrooted Trees
11
CSES 1674 Subordinates - Problem Statement
12
CSES 1674 Subordinates - Core Idea
13
CSES 1674 Subordinates - Recurrence
14
CSES 1674 Subordinates - Algorithm
15
CSES 1674 Subordinates - Implementation
16
CSES 1674 Subordinates - Walkthrough
17
CSES 1674 Subordinates - Lessons
18
Quiz: Subordinates Problem
19
Include/Exclude Pattern
20
Include/Exclude Transitions
21
LeetCode 337 House Robber III - Problem Statement
22
LeetCode 337 House Robber III - State Definition
23
LeetCode 337 House Robber III - Recurrence
24
LeetCode 337 House Robber III - Base Case
25
LeetCode 337 House Robber III - Implementation
26
LeetCode 337 House Robber III - Walkthrough
27
LeetCode 337 House Robber III - Lessons
28
Quiz: Include/Exclude Pattern
29
Path Problems on Trees
30
Combining Paths from Children
31
LeetCode 124 Binary Tree Maximum Path Sum - Problem Statement
32
LeetCode 124 Binary Tree Maximum Path Sum - State Definition
33
LeetCode 124 Binary Tree Maximum Path Sum - Core Idea
34
LeetCode 124 Binary Tree Maximum Path Sum - Handling Negatives
35
LeetCode 124 Binary Tree Maximum Path Sum - Algorithm
36
LeetCode 124 Binary Tree Maximum Path Sum - Implementation
37
LeetCode 124 Binary Tree Maximum Path Sum - Walkthrough
38
LeetCode 124 Binary Tree Maximum Path Sum - Lessons
39
Quiz: Path Problems
40
Rerooting Technique Preview
41
Common Mistakes in Tree DP
42
Tree DP vs Graph DP
43
When to Use Subtree DP
44
Section Recap
Floyd-Warshall Algorithm
0/41
1
Intro
2
The All-Pairs Problem
3
Naive Approach
4
The Core Idea
5
The DP State
6
Space Improvement
7
Quiz: Floyd-Warshall DP State
8
Why k is Outermost
9
The Algorithm
10
Time Complexity
11
Handling Negative Edges
12
Detecting Negative Cycles
13
Quiz: Negative Edges in Floyd-Warshall
14
Path Reconstruction
15
Transitive Closure
16
When to Use Floyd-Warshall
17
Quiz: When to Use Floyd-Warshall
18
CSES 1672 Shortest Routes II - Problem Statement
19
CSES 1672 Shortest Routes II - Why Floyd-Warshall Fits
20
CSES 1672 Shortest Routes II - Handling Multiple Edges
21
CSES 1672 Shortest Routes II - Implementation
22
CSES 1672 Shortest Routes II - Walkthrough
23
CSES 1672 Shortest Routes II - Lessons
24
LeetCode 1334 Find the City - Problem Statement
25
LeetCode 1334 Find the City - Breaking Down the Problem
26
LeetCode 1334 Find the City - Counting Reachable Cities
27
LeetCode 1334 Find the City - Implementation
28
LeetCode 1334 Find the City - Walkthrough
29
LeetCode 1334 Find the City - Lessons
30
Quiz: Floyd-Warshall Path Reconstruction
31
Common Mistakes
32
Floyd-Warshall vs Bellman-Ford
33
Floyd-Warshall vs Johnson's Algorithm
34
Practical Constraints
35
Memory Layout
36
Infinity Handling
37
Undirected Graphs
38
Variants of Floyd-Warshall
39
Quiz: Floyd-Warshall Loop Order
40
Practice Problems
41
Section Recap
Dijkstra's Algorithm
0/40
1
Intro
2
Introducing Weights
3
The Greedy Strategy
4
Dijkstra's Algorithm - Setup
5
Dijkstra's Algorithm - The Loop
6
The Relaxation Step
7
Quiz: Dijkstra's Greedy Choice
8
Relaxation in Code
9
Dijkstra - Implementation
10
Complexity of Dijkstra
11
Path Reconstruction in Dijkstra
12
Handling Large Weights
13
Quiz: Why Negative Edges Break Dijkstra
14
LeetCode 743 Network Delay Time - Problem Statement
15
LeetCode 743 Network Delay Time - Intuition
16
LeetCode 743 Network Delay Time - Implementation
17
CSES 1671 Shortest Routes I - Problem Statement
18
LeetCode 1514 Path with Maximum Probability - Problem Statement
19
LeetCode 1514 Path with Maximum Probability - Modifying Dijkstra
20
Quiz: Dijkstra Modifications
21
LeetCode 787 Cheapest Flights Within K Stops - Problem Statement
22
LeetCode 787 Cheapest Flights Within K Stops - State Definition
23
LeetCode 787 Cheapest Flights Within K Stops - Algorithm
24
LeetCode 787 Cheapest Flights Within K Stops - Visited Set
25
LeetCode 787 Cheapest Flights Within K Stops - Implementation
26
LeetCode 787 Cheapest Flights Within K Stops - Lessons
27
Quiz: Dijkstra with Constraints
28
LeetCode 1631 Path with Minimum Effort - Problem Statement
29
LeetCode 1631 Path with Minimum Effort - Minimax Path
30
LeetCode 1631 Path with Minimum Effort - Algorithm
31
LeetCode 1631 Path with Minimum Effort - Priority Queue
32
LeetCode 1631 Path with Minimum Effort - Implementation
33
LeetCode 1631 Path with Minimum Effort - Lessons
34
Quiz: Dijkstra on Grids
35
CSES 1195 Flight Discount - Problem Statement
36
CSES 1195 Flight Discount - State Definition
37
CSES 1195 Flight Discount - Algorithm
38
CSES 1195 Flight Discount - Implementation
39
CSES 1195 Flight Discount - Lessons
40
Section Recap
Bellman-Ford Algorithm
0/48
1
Intro
2
When Dijkstra Fails
3
The Relaxation Operation
4
Bellman-Ford Strategy
5
Why $n-1$ Iterations
6
Basic Bellman-Ford Implementation
7
Time Complexity Analysis
8
Quiz: Relaxation and Iterations
9
Detecting Negative Cycles
10
Finding Affected Nodes
11
CSES 1673 High Score - Problem Statement
12
CSES 1673 High Score - Negating Weights
13
CSES 1673 High Score - Detecting Positive Cycles
14
CSES 1673 High Score - Two-Way Reachability
15
CSES 1673 High Score - Algorithm
16
CSES 1673 High Score - Implementation
17
CSES 1673 High Score - Walkthrough
18
CSES 1673 High Score - Lessons
19
Quiz: Negative Cycle Reachability
20
CSES 1197 Cycle Finding - Problem Statement
21
CSES 1197 Cycle Finding - Parent Tracking
22
CSES 1197 Cycle Finding - Finding Cycle Start
23
CSES 1197 Cycle Finding - Algorithm
24
CSES 1197 Cycle Finding - Implementation
25
CSES 1197 Cycle Finding - Walkthrough
26
CSES 1197 Cycle Finding - Lessons
27
Quiz: Cycle Reconstruction
28
LeetCode 787 Cheapest Flights Within K Stops - Problem Statement
29
LeetCode 787 Cheapest Flights Within K Stops - Layer-by-Layer Relaxation
30
LeetCode 787 Cheapest Flights Within K Stops - Temporal Separation
31
LeetCode 787 Cheapest Flights Within K Stops - Algorithm
32
LeetCode 787 Cheapest Flights Within K Stops - Implementation
33
LeetCode 787 Cheapest Flights Within K Stops - Walkthrough
34
LeetCode 787 Cheapest Flights Within K Stops - Lessons
35
Quiz: Bounded Relaxation
36
SPFA Improvement
37
SPFA Implementation
38
SPFA Cycle Detection
39
When to Use Bellman-Ford
40
Application: Currency Arbitrage
41
Quiz: Algorithm Selection
42
Application: Network Routing
43
Edge Cases and Mistakes
44
Comparison Summary
45
Common Mistakes
46
Quiz: SPFA Worst Case
47
Practice Strategy
48
Section Recap
Mixed Practice - Shortest Paths
0/36
1
Intro
2
The Decision Tree
3
Quiz: Algorithm Selection
4
When BFS Wins
5
When Dijkstra Wins
6
Quiz: Dijkstra Traps
7
When Bellman-Ford Wins
8
Negative Cycles: The Trap
9
Quiz: Negative Cycles
10
When Floyd-Warshall Wins
11
CSES 1671 Shortest Routes I - Problem Statement
12
CSES 1671 Shortest Routes I - Recognizing Dijkstra
13
CSES 1671 Shortest Routes I - Implementation Notes
14
Quiz: Dijkstra Optimization
15
CSES 1671 Shortest Routes I - Implementation
16
CSES 1673 High Score - Problem Statement
17
CSES 1673 High Score - The Maximum-Score Trick
18
CSES 1673 High Score - The Reachability Trap
19
Quiz: Negative Cycle Impact
20
CSES 1673 High Score - Implementation
21
CSES 1195 Flight Discount - Problem Statement
22
CSES 1195 Flight Discount - State-Space Graphs
23
CSES 1195 Flight Discount - Transitions
24
Quiz: State Graph Size
25
CSES 1195 Flight Discount - Implementation
26
CSES 1202 Investigation - Problem Statement
27
CSES 1202 Investigation - Counting During Dijkstra
28
CSES 1202 Investigation - Update Rules
29
Quiz: Counting Paths
30
CSES 1202 Investigation - Implementation
31
Codeforces 295B Greg and Graph - Problem Statement
32
Codeforces 295B Greg and Graph - The Reverse Trick
33
Codeforces 295B Greg and Graph - Floyd-Warshall Incremental
34
Quiz: Reverse Processing
35
Codeforces 295B Greg and Graph - Implementation
36
Section Recap
Disjoint Set Union (DSU)
0/49
1
Intro
2
Disjoint Set Union (DSU)
3
The Intuition - Leaders
4
The Parent Array
5
The Find Operation
6
The Union Operation
7
The Problem with Naive DSU
8
Improvement 1 - Path Compression
9
Implementation - Find with Compression
10
Quiz: Path Compression
11
Improvement 2 - Union by Size
12
Implementation - Union by Size
13
The Full DSU Template
14
Cycle Detection
15
Quiz: Cycle Detection with DSU
16
LeetCode 684 Redundant Connection - Problem Statement
17
LeetCode 684 Redundant Connection - Logic
18
Counting Components
19
LeetCode 547 Number of Provinces - Problem Statement
20
LeetCode 547 Number of Provinces - Strategy
21
Tracking Component Sizes
22
CSES 1676 Road Construction - Problem Statement
23
CSES 1676 Road Construction - Logic
24
Pattern - Logic & Equations
25
Quiz: Component Counting
26
LeetCode 990 Satisfiability of Equality Equations - Problem Statement
27
LeetCode 990 Satisfiability of Equality Equations - Strategy
28
Pattern - Transitivity
29
LeetCode 1202 Smallest String With Swaps - Problem Statement
30
LeetCode 1202 Smallest String With Swaps - Algorithm
31
Pattern - Indirect Grouping
32
LeetCode 721 Accounts Merge - Problem Statement
33
LeetCode 721 Accounts Merge - The Graph
34
Pattern - Grid Components
35
Quiz: Indirect Grouping
36
LeetCode 827 Making A Large Island - Problem Statement
37
LeetCode 827 Making A Large Island - Logic
38
Pattern - Hub Nodes
39
Codeforces 1263D Secret Passwords - Problem Statement
40
Codeforces 1263D Secret Passwords - Logic
41
Pattern - Offline Queries
42
Quiz: Offline Processing
43
LeetCode 1697 Edge Limited Paths - Problem Statement
44
LeetCode 1697 Edge Limited Paths - Implementation Plan
45
Pattern - The Reverse Time Trick
46
USACO 644 Closing the Farm - Problem Statement
47
USACO 644 Closing the Farm - Solution
48
Quiz: Reverse Time Trick
49
Section Recap
Minimum Spanning Trees
0/48
1
Intro
2
What is a Spanning Tree?
3
Minimum Spanning Tree (MST)
4
The Cut Property
5
The Cycle Property
6
Kruskal's Algorithm - Idea
7
Kruskal with Union-Find
8
Kruskal's Time Complexity
9
Kruskal's Algorithm - Pseudocode
10
Prim's Algorithm - Idea
11
Prim with Priority Queue
12
Prim's Time Complexity
13
Prim's Algorithm - Pseudocode
14
Kruskal vs Prim - When to Use Each
15
MST in Disconnected Graphs
16
Problem - Road Reparation
17
Problem - Read Statement
18
Core Idea - Check Connectivity
19
Core Idea - Kruskal is Perfect Here
20
Algorithm - Kruskal with Validation
21
Road Reparation - Implementation
22
Problem - Implement Solution
23
Walkthrough - Road Reparation
24
Lessons from Road Reparation
25
Problem - Min Cost to Connect All Points
26
Problem - Read Statement
27
Core Idea - Complete Graph
28
Core Idea - Manhattan Distance
29
Algorithm - Prim on Implicit Graph
30
Min Cost Connect - Implementation
31
Problem - Implement Solution
32
Walkthrough - Min Cost Connect
33
Lessons from Min Cost Connect
34
Problem - Building Roads
35
Problem - Read Statement
36
Core Idea - Find Components
37
Core Idea - Connect Component Representatives
38
Algorithm - Component Chaining
39
Building Roads - Implementation
40
Problem - Implement Solution
41
Walkthrough - Building Roads
42
Lessons from Building Roads
43
MST Uniqueness
44
Second-Best MST
45
MSTs in Practice
46
Quiz: Unique MST with Unique Weights
47
Quiz: Kruskal vs Prim on Dense Graphs
48
Section Recap
Topological Sort
0/41
1
Intro
2
Directed Acyclic Graphs (DAGs)
3
Kahn's Algorithm - The Intuition
4
Kahn's Algorithm - Implementation
5
Detecting Cycles with Kahn's
6
Quiz: Cycle Detection with Kahn's
7
Problem - Course Schedule II
8
Course Schedule II - The Constraint
9
Course Schedule II - Core Idea
10
Course Schedule II - Algorithm
11
Course Schedule II - Implementation
12
Lessons from Course Schedule II
13
DFS-Based Topological Sort
14
Comparing Kahn and DFS
15
Quiz: Kahn's vs DFS Topological Sort
16
Common Topological Sort Mistakes
17
Pattern - Lexicographical Order
18
Pattern - Uniqueness
19
Pattern - Implicit Graphs
20
Dynamic Programming on DAGs
21
Quiz: DAG Properties
22
Problem - Longest Flight Route
23
Longest Flight Route - Core Idea
24
Longest Flight Route - Algorithm
25
Longest Flight Route - Implementation
26
Pattern - Reverse Logic
27
Lessons from Longest Flight Route
28
Quiz: DP on DAGs
29
Problem - Game Routes
30
Game Routes - Core Idea
31
Game Routes - Algorithm
32
Game Routes - Implementation
33
Lessons from Game Routes
34
Quiz: Counting Paths in a DAG
35
Problem - Parallel Courses III
36
Parallel Courses III - Core Idea
37
Parallel Courses III - Algorithm
38
Parallel Courses III - Implementation
39
Lessons from Parallel Courses III
40
Quiz: Parallel Scheduling
41
Section Recap
DP on DAGs
0/50
1
Intro
2
Why DAGs Are Special
3
Topological Order Refresher
4
The DP on DAGs Pattern
5
Quiz: Topological Order
6
Shortest Path in DAGs
7
Defining the DP State
8
Shortest Path Algorithm
9
Shortest Path Example
10
Longest Path in DAGs
11
When You Need Longest Paths
12
Quiz: Path Types
13
Problem - Longest Flight Route
14
Core idea - Counting Nodes
15
Checking for Cycles
16
State Definition
17
Reconstructing the Route
18
Longest Flight Route - Implementation
19
Edge Case - Unreachable Destination
20
Walkthrough Example
21
Lessons Learned
22
Counting Paths
23
Problem - Game Routes
24
DP State for Counting
25
Why you Add Counts
26
Handling Large Counts
27
Game Routes - Implementation
28
Walkthrough Example
29
Quiz: Counting Paths
30
Common Mistake - Initialization
31
Common Mistake - Modulo Placement
32
Multiple Sources
33
Multiple Destinations
34
Backward DP
35
Combining Two DPs
36
Quiz: DP Details
37
Problem - High Score
38
Positive Cycles
39
Using Bellman-Ford
40
Cycles Must Be On Path
41
High Score - Implementation
42
When DAG DP Fails
43
DP on Trees
44
Vocabulary - Relaxation
45
Vocabulary - Topological Sort
46
Practice - Course Schedule II
47
Practice - Cheapest Flights
48
When to Use DP on DAGs
49
Implicit DAGs
50
Section Recap
Mixed Practice: Graph Traversals
0/35
1
Intro
2
The Decision Framework
3
Quiz: Pattern Recognition
4
Quiz: When DFS Fails
5
Problem - Message Route
6
Think About It
7
Quiz: Message Route Pattern
8
Message Route - Implementation
9
Problem - Labyrinth
10
Think About It
11
Quiz: Labyrinth Pattern
12
Labyrinth - Implementation
13
Problem - Course Schedule
14
Think About It
15
Quiz: Course Schedule Pattern
16
Course Schedule - Implementation
17
Problem - Round Trip
18
Think About It
19
Quiz: Round Trip Pattern
20
Round Trip - Implementation
21
Problem - Monsters
22
Think About It
23
Quiz: Monsters Pattern
24
Monsters - Implementation
25
Problem - Longest Flight Route
26
Think About It
27
Quiz: Longest Flight Route Pattern
28
Longest Flight Route - Implementation
29
Quiz: Technique Selection
30
Quiz: Grid Pattern Review
31
Quiz: DAG Pattern Review
32
Pattern Summary
33
Common Mistakes
34
Next Steps
35
Section Recap
Strongly Connected Components
0/45
1
Intro
2
What is an SCC?
3
Why Find SCCs?
4
Kosaraju's Algorithm - Intuition
5
Kosaraju's Algorithm - Steps
6
Kosaraju Example
7
Kosaraju - Implementation
8
Quiz: Kosaraju's First DFS
9
Tarjan's Algorithm - Intuition
10
Tarjan's Algorithm - Steps
11
Tarjan Example
12
Tarjan - Implementation
13
Kosaraju vs Tarjan
14
Quiz: Tarjan's Low-Link Values
15
The Condensation Graph
16
Building the Condensation Graph
17
Application: Dependency Analysis
18
Application: 2-SAT Connection
19
Quiz: Condensation Graph
20
Problem - Planets and Kingdoms (CSES 1683)
21
Planets and Kingdoms - Approach
22
Planets and Kingdoms - Implementation
23
Problem - Coin Collector (CSES 1686)
24
Coin Collector - Approach
25
Coin Collector - Implementation
26
Problem - Flight Routes Check (CSES 1682)
27
Flight Routes Check - Approach
28
Flight Routes Check - Implementation
29
Quiz: SCC Problem Solving
30
Edge Cases for SCC Problems
31
Common SCC Mistakes
32
SCC in Undirected Graphs?
33
When to Use SCC
34
Practice Problem 1
35
Practice Problem 2
36
Practice Problem 3
37
SCC and Bridges/Articulation Points
38
SCC in Real-World Graphs
39
Time Complexity Summary
40
Space Complexity Summary
41
SCC and Cycle Detection
42
SCC and Topological Sort
43
Quiz: SCC and Cycle Detection
44
SCC Templates
45
Section Recap
2-SAT
0/51
1
Intro
2
What is SAT
3
The 2-SAT Restriction
4
Variables and Negations
5
Implication Graphs
6
Converting OR to Implication
7
Why This Works
8
Example Conversion
9
Quiz: Implication Graph Construction
10
The SCC Connection
11
Why Same SCC Fails
12
Finding an Assignment
13
Why Topological Order Works
14
Algorithm Summary
15
Complexity Analysis
16
Quiz: Satisfiability Check
17
Problem - Giant Pizza
18
Modeling as 2-SAT
19
Building the Implication Graph
20
Checking Satisfiability
21
Constructing the Assignment
22
Giant Pizza - Implementation
23
Edge Case - All Positive
24
Edge Case - Contradiction
25
Lessons from Giant Pizza
26
Quiz: Assignment Construction
27
Constraint Pattern - At Most One
28
Constraint Pattern - Exactly One
29
Constraint Pattern - If-Then
30
Multiple Clauses on Same Variables
31
Quiz: Clause Conversion
32
Problem - Course Scheduling
33
Modeling Scheduling
34
Scheduling Solution
35
Lessons from Scheduling
36
When to Use 2-SAT
37
Extensions Beyond 2-SAT
38
Common Mistakes
39
Debugging 2-SAT Solutions
40
Quiz: Debugging 2-SAT
41
Vocabulary - Clause
42
Vocabulary - Literal
43
Vocabulary - Satisfiable
44
Vocabulary - Implication
45
Practice Problem 1
46
Practice Problem 2
47
Practice Problem 3
48
Visualization Tip
49
Connection to Other Topics
50
Quiz: Recognizing 2-SAT
51
Section Recap
Mixed Practice: Connectivity & MST
0/35
1
Intro
2
Core Decisions
3
SCC vs Bridges
4
MST vs DSU
5
Quiz: Pattern Signals
6
Quiz: Bidirectional Reachability
7
Problem - Road Construction
8
Recognizing DSU
9
Implementation - Road Construction
10
Quiz: Component Count
11
Problem - Road Reparation
12
Recognizing MST
13
Implementation - Road Reparation
14
Quiz: MST Edge Count
15
Problem - Flight Routes Check
16
Recognizing SCC
17
Implementation - Flight Routes Check
18
Quiz: SCC Count
19
Problem - Critical Connections
20
Recognizing Bridges
21
Implementation - Critical Connections
22
Quiz: Bridge Condition
23
Problem - Checkposts
24
Why SCC?
25
Implementation - Checkposts
26
Quiz: SCC Optimization
27
Problem - Edges in MST
28
Edge Classification
29
Implementation - Edges in MST
30
Quiz: MST Edge in ALL
31
Practice Strategy
32
Common Combinations
33
Quiz: Technique Pairing
34
Next Steps
35
Section Recap
Rerooting Technique
0/39
1
Intro
2
The Single-Root Problem (Why you need rerooting)
3
Rerooting Intuition (Reusing previous work)
4
The Two-Pass Algorithm (Down and up)
5
Down Pass (Computing subtree answers)
6
Up Pass (Propagating parent contributions)
7
Combining Down and Up (Final answers)
8
Contribution (What each subtree gives)
9
Prefix-Suffix Arrays (Excluding one child)
10
Rerooting Template (General pattern)
11
Problem - Tree Distances II (CSES 1133)
12
Core Observation (Moving root changes distances)
13
Down Pass (Subtree distances)
14
Up Pass (Parent contribution)
15
Final Answer (Combining down and up)
16
Tree Distances II - Implementation (Two DFS passes)
17
Walkthrough (Small tree example)
18
Lessons Learned (Sum aggregation)
19
Problem - Sum of Distances in Tree (LeetCode 834)
20
Implementation Notes (Array indexing)
21
Complexity Analysis (Linear time)
22
Rerooting vs Brute Force (Why rerooting wins)
23
When to Use Rerooting (Problem patterns)
24
State Design (What to track)
25
Handling Multiple Children (Prefix-suffix pattern)
26
Rerooting with Max (Not just sum)
27
Rerooting with Count (Combinatorial problems)
28
Edge Cases (Small trees)
29
Debugging Rerooting (Common mistakes)
30
Rerooting Variations (Different problems)
31
Practice Tips (Getting comfortable)
32
Quiz: Rerooting Answer
33
Quiz: Rerooting Up Value
34
Quiz: Rerooting Selection
35
Common Mistakes (What to avoid)
36
Rerooting in Contests (Recognition)
37
Advanced Rerooting (Multiple states)
38
Rerooting with Updates (Dynamic trees)
39
Section Recap
Euler Tour Technique
0/51
1
Intro
2
What is an Euler Tour
3
Entry and Exit Times
4
Subtrees as Ranges
5
Flattening the Tree
6
Basic Implementation
7
Example Tree
8
Quiz: Entry and Exit Times
9
Check Your Understanding
10
Problem - Subtree Queries
11
Core Idea - Subtree to Range
12
Core Idea - Which Times to Use
13
Algorithm
14
Subtree Queries - Implementation
15
Subtree Queries - Walkthrough
16
Lessons Learned
17
Quiz: Subtree as Range
18
Euler Tour Variants
19
Entry-Only Variant
20
Entry-Exit Variant
21
Full Tour Variant
22
Quiz: Euler Tour Variants
23
Check Your Understanding
24
Problem - Path Queries
25
Core Idea - Path as Prefix
26
Core Idea - Prefix Sum Trick
27
Algorithm
28
Path Queries - Implementation
29
Path Queries - Walkthrough
30
Lessons Learned
31
Quiz: Path Query Updates
32
Combining with Segment Trees
33
BIT as Lighter Alternative
34
Space Complexity
35
Update Types
36
Query Types
37
Ancestor Check
38
Rerooting Limitation
39
Check Your Understanding
40
DFS Order Matters
41
Quiz: Ancestor Check
42
Connection to Heavy-Light Decomposition
43
Practical Tips
44
Common Mistakes
45
Problem - Company Queries II
46
Core Idea - LCA via Euler Tour
47
Algorithm
48
Company Queries II - Implement Solution
49
Lessons Learned
50
Quiz: Combining with Data Structures
51
Section Recap
Mixed Practice: Tree Fundamentals
0/29
1
Intro
2
Decision Question 1
3
Decision Question 2
4
Quiz: Technique Selection
5
Problem - Subordinates
6
Think First
7
Quiz: Subordinates Technique
8
Subordinates - Implementation
9
Problem - Tree Diameter
10
Think First
11
Quiz: Diameter Approaches
12
Tree Diameter - Implementation
13
Problem - Tree Matching
14
Think First
15
Quiz: Matching States
16
Tree Matching - Implementation
17
Problem - Tree Distances II
18
Think First
19
Quiz: Rerooting Transition
20
Tree Distances II - Implementation
21
Problem - Choosing Capital
22
Think First
23
Quiz: Directed Transition
24
Choosing Capital - Implementation
25
Problem - Max White Subtree
26
Think First
27
Quiz: Max White Subtree
28
Max White Subtree - Implementation
29
Section Recap
Binary Lifting
0/50
1
Intro
2
The k-th Ancestor Problem
3
Naive Approach
4
Binary Representation Core Idea
5
Sparse Table Idea
6
Table Dimensions
7
Base Case - First Column
8
Recurrence Relation
9
Recurrence Example
10
Quiz: Sparse Table Construction
11
Building the Table
12
Building Code
13
Answering Queries
14
Query Pseudocode
15
Query Example
16
Quiz: Query Decomposition
17
Complexity Summary
18
Problem - Company Queries I
19
Core Idea - Tree Structure
20
Core Idea - Handling Invalid Queries
21
Algorithm
22
Company Queries I - Implementation
23
Walkthrough
24
Lessons Learned
25
Quiz: K-th Ancestor Edge Cases
26
Extension - LCA
27
Problem - Company Queries II
28
Core Idea - Same Depth First
29
Core Idea - Binary Search for LCA
30
Why This Works
31
Algorithm
32
Company Queries II - Implementation
33
Walkthrough
34
Walkthrough - Different Subtrees
35
Lessons Learned
36
Quiz: LCA via Binary Lifting
37
Problem - Kth Ancestor of a Tree Node
38
Core Idea - Constructor Preprocessing
39
Core Idea - Query Method
40
Algorithm
41
Kth Ancestor - Implementation
42
Walkthrough
43
Lessons Learned
44
Quiz: Time and Space Tradeoffs
45
Applications Beyond Ancestors
46
Space Improvement Note
47
Comparison to Naive Approach
48
Quiz: Binary Lifting Recurrence
49
Next Section Teaser
50
Section Recap
Lowest Common Ancestor (LCA)
0/51
1
Intro
2
What is LCA?
3
Why LCA Matters
4
Naive Approach - The Idea
5
Naive Approach - Implementation
6
Binary Lifting for LCA
7
Binary Lifting - Preprocessing
8
Core Idea - Binary Search on Ancestors
9
Binary Lifting - Climbing Together
10
Binary Lifting - Complexity
11
Problem - LCA of a Binary Tree
12
Problem - LCA of a Binary Tree - Read Statement
13
Core Idea - Multiple Approaches Exist
14
Core Idea - Base Cases
15
Algorithm - Recursive LCA
16
Implementation - Recursive LCA
17
Implementation - LCA of a Binary Tree - Implement Solution
18
Walkthrough - Example Tree
19
Lessons - Recursive Tree Traversal
20
Euler Tour for LCA
21
Euler Tour - Construction
22
LCA to RMQ Reduction
23
Sparse Table for RMQ
24
Sparse Table - Building
25
Sparse Table - Querying
26
Euler Tour + RMQ - Full Algorithm
27
Euler Tour + RMQ - Complexity
28
Distance Between Two Nodes
29
Problem - Distance Queries
30
Problem - Distance Queries - Read Statement
31
Core Idea - Precompute Depths and LCA
32
Implementation - Distance Queries
33
Implementation - Distance Queries - Implement Solution
34
Lessons - Amortized Preprocessing
35
Problem - Counting Paths
36
Problem - Counting Paths - Read Statement
37
Core Idea - Path as Range Update
38
Core Idea - Propagating Counts
39
Algorithm - Counting Paths
40
Implementation - Counting Paths
41
Implementation - Counting Paths - Implement Solution
42
Walkthrough - Example
43
Core Insight - Parent Decrement
44
Lessons - Difference Arrays on Trees
45
Path Queries Using LCA
46
Weighted Binary Lifting
47
Quiz: LCA Distance
48
Binary Lifting vs Euler Tour
49
Common Mistakes
50
Extensions
51
Section Recap
Games on Graphs
0/62
1
Intro
2
Positions as States
3
Winning vs Losing Positions
4
Terminal Positions
5
Backward Induction on DAGs
6
Why DAGs Are Simple
7
Quiz: Winning and Losing Positions
8
Games with Cycles
9
Classifying with Cycles
10
Implementation Pattern
11
Quiz: Backward Induction
12
Problem - Cat and Mouse (Part 1)
13
Problem - Cat and Mouse (Part 2)
14
Problem - Cat and Mouse (Part 3)
15
Problem - Cat and Mouse (Part 4)
16
Problem - Cat and Mouse (Part 5)
17
Problem - Cat and Mouse (Part 6)
18
Problem - Cat and Mouse (Part 7)
19
Problem - Cat and Mouse (Part 8)
20
Problem - Cat and Mouse (Part 9)
21
Problem - Cat and Mouse (Part 10)
22
Problem - Cat and Mouse (Part 11)
23
Problem - Cat and Mouse (Part 12)
24
Two-Player vs Single-Player
25
Nim-Like Games on Graphs
26
Computing Grundy Numbers
27
When to Use Grundy
28
Quiz: Sprague-Grundy Values
29
Pursuit-Evasion Games
30
Cops and Robbers on Trees
31
Cops and Robbers on General Graphs
32
Problem - Coin Game on DAG (Part 1)
33
Problem - Coin Game on DAG (Part 2)
34
Problem - Coin Game on DAG (Part 3)
35
Problem - Coin Game on DAG (Part 4)
36
Problem - Coin Game on DAG (Part 5)
37
Problem - Coin Game on DAG (Part 6)
38
Move Ordering Strategies
39
Distance to Win
40
Minimax on Graphs
41
Alpha-Beta Pruning
42
Quiz: Minimax on Graphs
43
Memoization for Graph Games
44
Problem - Game on Tree (Part 1)
45
Problem - Game on Tree (Part 2)
46
Problem - Game on Tree (Part 3)
47
Problem - Game on Tree (Part 4)
48
Infinite Games
49
Draw Detection Strategies
50
Quiz: Draw Detection in Cyclic Games
51
Bipartite Game Graphs
52
Applications in AI
53
Applications in Network Security
54
Applications in Robotics
55
Stochastic Games
56
Complexity of Game Analysis
57
When to Use Game Theory
58
Common Mistakes
59
Quiz: Game State Representation
60
Debugging Game Code
61
Extensions and Variants
62
Section Recap
Heavy-Light Decomposition
0/49
1
Intro
2
The Path Query Problem
3
Why Subtree Tricks Fail
4
The Chain Idea
5
Subtree Size
6
Heavy and Light Edges
7
Heavy Paths as Chains
8
The $O(\log n)$ Chain Property
9
Path to LCA Structure
10
Chain Decomposition DFS
11
Chain Positions
12
Chain Heads
13
Segment Tree per Chain
14
Single Segment Tree Improvement
15
Path Query Algorithm
16
Depth Array
17
Parent Array
18
Update Operation
19
Edge Queries vs Vertex Queries
20
LCA in HLD
21
Complexity Analysis
22
Implementation - Preprocessing
23
Implementation - Decomposition
24
Implementation - Segment Tree
25
Implementation - Path Query
26
Path Updates
27
Path Sum Queries
28
Problems - Path Queries II - Read Statement
29
Path Queries II - Heavy Edges
30
Path Queries II - Segment Tree
31
Path Queries II - Query Algorithm
32
Path Queries II - Update Algorithm
33
Path Queries II - Complexity
34
Path Queries II - Implementation
35
Path Queries II - Lessons
36
Problems - QTREE - Read Statement
37
QTREE - Edge to Vertex Mapping
38
QTREE - Query Path Edges
39
QTREE - Edge Update
40
QTREE - Complexity
41
QTREE - Implementation Notes
42
QTREE - Lessons
43
When to Use HLD
44
HLD vs LCA Binary Lifting
45
Common Mistakes
46
Quiz: Heavy Edge Definition
47
Quiz: Chain Crossing Bound
48
Quiz: Query Complexity
49
Section Recap
Centroid Decomposition
0/55
1
Intro
2
Why Centroid Decomposition?
3
What is a Centroid?
4
Centroid Existence Proof
5
Finding the Centroid
6
Example: Finding a Centroid
7
Centroid Properties
8
Quiz: Centroid Properties
9
The Centroid Decomposition Tree
10
Why Depth is O(log n)
11
Quiz: Decomposition Tree Depth
12
Building the Decomposition Tree
13
Decomposition Tree vs Original Tree
14
Paths Through Centroids
15
Divide and Conquer on Trees
16
Problem - Finding a Centroid
17
Read Statement
18
Core idea 1 - Subtree Sizes
19
Core idea 2 - Walk to Heavy Subtree
20
Algorithm - Find Centroid
21
Finding a Centroid - Implementation
22
Walkthrough
23
Lessons Learned
24
Quiz: Finding the Centroid
25
Problem - Fixed-Length Paths I
26
Read Statement
27
Core idea 1 - Paths Through Centroid
28
Core idea 2 - Combining Subtree Paths
29
Core idea 3 - Subtract Same-Subtree Paths
30
Algorithm - Count Paths Through Centroid
31
Fixed-Length Paths I - Implementation
32
Walkthrough
33
Lessons Learned
34
Quiz: Counting Paths Through Centroid
35
Problem - Fixed-Length Paths II
36
Read Statement
37
Core idea - Count Range Instead of Exact
38
Algorithm - Count Paths in Range
39
Fixed-Length Paths II - Implementation
40
Walkthrough
41
Lessons Learned
42
Distance Queries with Centroid Decomposition
43
When to Use Centroid Decomposition
44
Quiz: When to Apply Centroid Decomposition
45
Centroid Decomposition vs Other Techniques
46
Implementation Tips
47
Complexity Analysis
48
Space Complexity
49
Variations and Extensions
50
Debugging Centroid Decomposition
51
Practice Problems
52
Check Your Understanding
53
Check Your Understanding
54
Check Your Understanding
55
Section Recap
Small-to-Large Merging
0/40
1
Intro
2
The Merging Problem
3
Naive Merging
4
Worst Case: Chain Tree
5
The Core idea
6
Why O(n log n) Works
7
Implementation Pattern
8
Code Structure
9
Tracking Subtree Sizes
10
Reusing the Largest Set
11
Problem - Distinct Colors
12
Distinct Colors - Naive Approach
13
Distinct Colors - Algorithm
14
Distinct Colors - Implementation
15
Distinct Colors - Walkthrough
16
Distinct Colors - Lessons
17
Problem - Lomsat gelral
18
Lomsat gelral - Observation
19
Lomsat gelral - Algorithm
20
Lomsat gelral - Maintaining the Max
21
Lomsat gelral - Implementation
22
Lomsat gelral - Walkthrough
23
Lomsat gelral - Lessons
24
When to Use Small-to-Large
25
Alternatives to Small-to-Large
26
Memory Considerations
27
Connection to Heavy-Light Decomposition
28
Implementation Tips
29
Debugging Small-to-Large
30
Quiz: Small-to-Large Complexity
31
Quiz: Small-to-Large Use
32
Variations of the Technique
33
Practice Tips
34
Common Problem Variations
35
Online vs Offline
36
Space Improvement
37
Constant Factors
38
Combining with Other Techniques
39
Historical Note
40
Section Recap
Functional Graphs
0/47
1
Intro
2
Function Notation
3
The Rho Shape
4
Example Graph
5
Why This Matters
6
Floyd's Algorithm
7
Floyd's Implementation
8
Finding Cycle Start
9
Why Floyd Works
10
Cycle Length
11
Problem - Linked List Cycle II
12
Core Idea - Two-Phase Approach
13
Core Idea - Null Pointer Check
14
Linked List Cycle II - Implementation
15
Linked List Cycle II - Walkthrough
16
Linked List Cycle II - Lessons
17
Binary Lifting for Successors
18
Preprocessing Table
19
Query Processing
20
Problem - Planets Queries I
21
Core Idea - Preprocessing Once
22
Core Idea - Binary Representation
23
Planets Queries I - Implementation
24
Planets Queries I - Walkthrough
25
Planets Queries I - Lessons
26
Quiz: Functional Graph Distances
27
Tail vs Cycle Position
28
Precomputing Cycle Info
29
Distance Query Cases
30
Problem - Planets Queries II
31
Core Idea - Cycle Membership
32
Core Idea - Distance to Cycle
33
Core Idea - Cycle Position Index
34
Planets Queries II - Walkthrough
35
Planets Queries II - Lessons
36
Problem - Planet Cycles
37
Core Idea - DFS with Memoization
38
Core Idea - Color-Based Detection
39
Planet Cycles - Walkthrough
40
Planet Cycles - Lessons
41
Permutation Cycles
42
Cycle Decomposition
43
Application - Sorting with Swaps
44
Application - Josephus Problem
45
Space Improvement
46
Common Mistakes
47
Section Recap
Mixed Practice: Advanced Tree Techniques
0/36
1
Intro
2
Reading the Clues
3
Subtree vs Path Queries
4
Counting vs Computing
5
Merging Information
6
Problem - Company Queries II
7
Think First - Company Queries II
8
Quiz: Company Queries II
9
Reveal - Company Queries II
10
Company Queries II - Implementation
11
Lessons - Company Queries II
12
Problem - Path Queries II
13
Think First - Path Queries II
14
Quiz: Path Queries II
15
Reveal - Path Queries II
16
Path Queries II - Implementation
17
Lessons - Path Queries II
18
Problem - Blood Cousins
19
Think First - Blood Cousins
20
Quiz: Blood Cousins
21
Reveal - Blood Cousins
22
Blood Cousins - Implementation
23
Lessons - Blood Cousins
24
Problem - Lomsat gelral
25
Think First - Lomsat gelral
26
Quiz: Lomsat gelral
27
Reveal - Lomsat gelral
28
Lomsat gelral - Implementation
29
Lessons - Lomsat gelral
30
Problem - Fixed-Length Paths I
31
Think First - Fixed-Length Paths I
32
Quiz: Fixed-Length Paths I
33
Reveal - Fixed-Length Paths I
34
Fixed-Length Paths I - Implementation
35
Lessons - Fixed-Length Paths I
36
Section Recap
Bridges and Articulation Points
0/58
1
Intro
2
What is a Bridge?
3
Bridge Example
4
Why Bridges Matter
5
What is an Articulation Point?
6
Articulation Point Example
7
DFS Tree and Back Edges
8
DFS Tree Example
9
Why Back Edges Prevent Bridges
10
Discovery Time
11
Low-Link Value
12
Low-Link Intuition
13
Low-Link Example
14
Quiz: Low-Link Values
15
Tarjan's Algorithm for Bridges
16
Bridge Detection Logic
17
Tarjan Bridge Pseudocode
18
Bridge Algorithm Walkthrough
19
Quiz: Bridge Detection Condition
20
Tarjan's Algorithm for Articulation Points
21
Articulation Point: Root Case
22
Articulation Point: Non-Root Case
23
Articulation Point Pseudocode
24
Articulation Point Walkthrough
25
Quiz: Articulation Point Rules
26
Vocabulary - Critical Connection
27
Problem - Critical Connections in a Network
28
Critical Connections - Input Example
29
Critical Connections - Core Idea
30
Critical Connections - Algorithm
31
Critical Connections - Implementation
32
Critical Connections - Trace
33
Critical Connections - Time Complexity
34
Critical Connections - Edge Cases
35
Critical Connections - Lessons
36
Vocabulary - 2-Edge-Connected Component
37
Building 2-Edge-Connected Components
38
2-Edge-Connected Components Example
39
Quiz: $2$-Edge-Connected Components
40
Problem - Finding Articulation Points
41
Articulation Points - Input Example
42
Articulation Points - Core idea
43
Articulation Points - Algorithm
44
Articulation Points - Implementation
45
Articulation Points - Trace
46
Articulation Points - Time Complexity
47
Articulation Points - Edge Cases
48
Articulation Points - Lessons
49
Quiz: Tarjan's Algorithm Complexity
50
Application - Network Reliability
51
Application - Graph Partitioning
52
Application - Circuit Design
53
Vocabulary - Biconnected Component
54
Building Biconnected Components
55
Bridge Trees
56
Quiz: Bridge Trees
57
Bridge Tree Example
58
Section Recap
Network Flow
0/54
1
Intro
2
Flow Networks
3
Flow Assignment
4
Example Flow
5
The Max Flow Problem
6
Residual Graph
7
Augmenting Path
8
Quiz: Residual Graph
9
Ford-Fulkerson Method
10
Why It Works
11
Edmonds-Karp Algorithm
12
Pseudocode - Edmonds-Karp
13
Residual Capacity Update
14
Implementation Details
15
Time Complexity
16
Quiz: Edmonds-Karp Complexity
17
Problem - Download Speed
18
Download Speed - Modeling
19
Download Speed - Implementation
20
Download Speed - Walkthrough
21
Download Speed - Edge Cases
22
Cuts and Capacity
23
Min-Cut
24
Max-Flow Min-Cut Theorem
25
Finding the Min-Cut
26
Quiz: Max-Flow Min-Cut Theorem
27
Problem - Police Chase
28
Police Chase - Core Idea
29
Police Chase - Extracting the Cut
30
Police Chase - Implementation
31
Police Chase - Walkthrough
32
Bipartite Matching
33
Problem - School Dance
34
School Dance - Graph Construction
35
School Dance - Extracting Pairs
36
School Dance - Implementation
37
School Dance - Walkthrough
38
School Dance - Edge Cases
39
Quiz: Bipartite Matching via Flow
40
Multiple Sources and Sinks
41
Vertex Capacities
42
Flow with Lower Bounds
43
Integer Flow Theorem
44
Disjoint Paths
45
When to Use Flow
46
Common Mistakes
47
Quiz: Node Capacity Modeling
48
Faster Algorithms
49
Flow in Practice
50
Vocabulary - Augmenting Path
51
Vocabulary - Residual Graph
52
Vocabulary - Cut
53
Practice Tips
54
Section Recap
Maximum Bipartite Matching
0/50
1
Intro
2
What Is a Matching
3
Maximum Matching
4
Perfect Matching
5
Augmenting Paths
6
Why Augmenting Paths Work
7
Finding Augmenting Paths
8
Quiz: Augmenting Paths in Matching
9
Kuhn's Algorithm
10
Kuhn's Algorithm - Pseudocode
11
Problem - School Dance
12
Problem - School Dance - Read Statement
13
School Dance - Core Idea
14
School Dance - Algorithm
15
School Dance - Implementation
16
School Dance - Walkthrough
17
School Dance - Lessons
18
Quiz: Kuhn's Algorithm Complexity
19
Reduction to Max Flow
20
Why Max Flow Works
21
König's Theorem
22
Proof Idea of König's Theorem
23
Hall's Marriage Theorem
24
Checking Hall's Condition
25
Quiz: Hall's Marriage Theorem
26
Application - Job Assignment
27
Application - Scheduling
28
Problem - Maximum Matching
29
Maximum Matching - Core Idea
30
Maximum Matching - Implementation
31
Maximum Matching - Walkthrough
32
Maximum Matching - Lessons
33
Problem - Assign Cookies
34
Assign Cookies - Greedy Solution
35
Assign Cookies - Matching Solution
36
Assign Cookies - Implementation
37
Assign Cookies - Lessons
38
Quiz: Konig's Theorem
39
Weighted Bipartite Matching
40
Online Bipartite Matching
41
Common Mistakes
42
Improvement - Early Termination
43
Hopcroft-Karp Algorithm
44
When to Use Each Algorithm
45
Minimum Vertex Cover from Matching
46
Minimum Edge Cover
47
Maximum Independent Set
48
Quiz: Matching and Independence
49
Checklist - Bipartite Matching
50
Section Recap
Minimum Cut
0/47
1
Intro
2
What is a Cut?
3
Cut Capacity
4
s-t Cut
5
Minimum s-t Cut
6
Max-Flow Min-Cut Theorem
7
Theorem Intuition
8
Quiz: Max-Flow Min-Cut Relationship
9
Finding the Min Cut
10
Algorithm - Find Min Cut
11
Why Residual Graph Works
12
Example - Finding Min Cut
13
Quiz: Finding Cut Edges
14
Global Minimum Cut
15
Stoer-Wagner Algorithm
16
Edge Connectivity
17
Vertex Connectivity
18
Application - Network Reliability
19
Application - Image Segmentation
20
Application - Clustering
21
Quiz: Stoer-Wagner Algorithm
22
Problem - Police Chase
23
Problem - Police Chase - Read Statement
24
Core Idea - Max Flow with Unit Capacities
25
Core Idea - Extracting the Cut Edges
26
Handling Bidirectional Roads
27
Implementation - Police Chase
28
Implementation - Police Chase - Implement Solution
29
Lessons - Min Cut Applications
30
Quiz: Vertex vs Edge Connectivity
31
Problem - Distinct Routes
32
Problem - Distinct Routes - Read Statement
33
Core Idea - Max Flow Equals Path Count
34
Core Idea - Flow Decomposition
35
Algorithm - Path Decomposition
36
Implementation - Distinct Routes
37
Implementation - Distinct Routes - Implement Solution
38
Lessons - Flow Decomposition
39
Problem - Network Segmentation
40
Core Idea - Try All Pairs
41
Core Idea - Stoer-Wagner Basics
42
Maximum Adjacency Ordering
43
Algorithm - Stoer-Wagner
44
Quiz: Maximum Adjacency Ordering
45
Implementation - Network Segmentation
46
Lessons - Global vs Local Cuts
47
Section Recap
Euler Paths and Circuits
0/37
1
Intro
2
What is an Euler Path
3
What is an Euler Circuit
4
Conditions for Undirected Graphs
5
Conditions for Directed Graphs
6
Quiz: Euler Path Conditions
7
Checking Eulerian Conditions
8
Hierholzer's Algorithm
9
Hierholzer's Pseudocode
10
Why Hierholzer Works
11
Quiz: Hierholzer's Algorithm
12
Time and Space Complexity
13
Problem - Mail Delivery
14
Mail Delivery - Core idea
15
Mail Delivery - Algorithm
16
Mail Delivery - Implementation
17
Mail Delivery - Lessons
18
Quiz: Directed Euler Path Conditions
19
Problem - Teleporters Path
20
Teleporters Path - Core idea
21
Teleporters Path - Implementation
22
Teleporters Path - Lessons
23
Problem - Reconstruct Itinerary
24
Reconstruct Itinerary - Core idea
25
Reconstruct Itinerary - Implementation
26
Quiz: Lexicographic Euler Path
27
De Bruijn Sequences
28
Problem - De Bruijn Sequence
29
De Bruijn Sequence - Core idea
30
De Bruijn Sequence - Implementation
31
Quiz: De Bruijn Sequences
32
Problem - Cracking the Safe
33
Cracking the Safe - Core idea
34
Chinese Postman Problem
35
Applications
36
Common Mistakes
37
Section Recap
Mixed Practice: Advanced Graphs
0/24
1
Intro
2
Decision Framework
3
Pattern: SCC Applications
4
Pattern: 2-SAT
5
Pattern: Functional Graphs
6
Pattern: Hamiltonian vs Euler
7
Problem - Coin Collector
8
Coin Collector - Analysis
9
Coin Collector - Implementation
10
Problem - Giant Pizza
11
Giant Pizza - Analysis
12
Giant Pizza - Implementation
13
Problem - Planets Queries II
14
Planets Queries II - Analysis
15
Planets Queries II - Implementation
16
Problem - Hamiltonian Flights
17
Hamiltonian Flights - Analysis
18
Hamiltonian Flights - Implementation
19
Problem - Knight's Tour
20
Knight's Tour - Analysis
21
Knight's Tour - Implementation
22
Quiz: Pattern Recognition
23
Common Mistakes
24
Section Recap