What topics does this roadmap cover?

Graph Fundamentals, Depth First Search (DFS), Breadth First Search (BFS), Flood Fill & Grid Graphs, Bipartite Graphs, Tree Fundamentals, Tree Diameter & Center, Subtree DP, Floyd-Warshall Algorithm, Dijkstra's Algorithm, Bellman-Ford Algorithm, Mixed Practice - Shortest Paths, Disjoint Set Union (DSU), Minimum Spanning Trees, Topological Sort, DP on DAGs, Mixed Practice: Graph Traversals, Strongly Connected Components, 2-SAT, Mixed Practice: Connectivity & MST, Rerooting Technique, Euler Tour Technique, Mixed Practice: Tree Fundamentals, Binary Lifting, Lowest Common Ancestor (LCA), Games on Graphs, Heavy-Light Decomposition, Centroid Decomposition, Small-to-Large Merging, Functional Graphs, Mixed Practice: Advanced Tree Techniques, Bridges and Articulation Points, Network Flow, Maximum Bipartite Matching, Minimum Cut, Euler Paths and Circuits, Mixed Practice: Advanced Graphs

How many units are in this roadmap?

This roadmap contains 1633 units across 37 sections.

Is this roadmap free?

Yes, this roadmap is completely free.

Graph Theory - Roadmaps

Disjoint Set Union (DSU)

Union by rank/size, path compression, rollback DSU, and applications.

Intro

Dynamic changes

Disjoint Set Union (DSU)

The Structure

The Intuition - Leaders

Who is the boss?

The Parent Array

Tracking relationships

The Find Operation

Finding the Leader

The Union Operation

Merging Groups

The Problem with Naive DSU

Long Chains

Improvement 1 - Path Compression

The Magic Step

Implementation - Find with Compression

Coding the Magic

Quiz: Path Compression

Knowledge check

Improvement 2 - Union by Size

Balancing the Tree

Implementation - Union by Size

Coding the Merger

The Full DSU Template

Copy-Paste Ready

Cycle Detection

Application 1

Quiz: Cycle Detection with DSU

Knowledge check

LeetCode 684 Redundant Connection - Problem Statement

LeetCode 684

LeetCode 684 Redundant Connection - Logic

First Hit

Counting Components

Application 2

LeetCode 547 Number of Provinces - Problem Statement

LeetCode 547 (DSU Version)

LeetCode 547 Number of Provinces - Strategy

Iterating the Matrix

Tracking Component Sizes

Application 3

CSES 1676 Road Construction - Problem Statement

CSES Problem Set

CSES 1676 Road Construction - Logic

Maintaining State

Pattern - Logic & Equations

Symbols as Nodes

Quiz: Component Counting

Knowledge check

LeetCode 990 Satisfiability of Equality Equations - Problem Statement

LeetCode 990

LeetCode 990 Satisfiability of Equality Equations - Strategy

Two Passes

Pattern - Transitivity

Swapping Logic

LeetCode 1202 Smallest String With Swaps - Problem Statement

LeetCode 1202

LeetCode 1202 Smallest String With Swaps - Algorithm

Sorting Components

Pattern - Indirect Grouping

Mapping Data

LeetCode 721 Accounts Merge - Problem Statement

LeetCode 721

LeetCode 721 Accounts Merge - The Graph

Emails are Edges

Pattern - Grid Components

Connecting pixels

Quiz: Indirect Grouping

Knowledge check

LeetCode 827 Making A Large Island - Problem Statement

LeetCode 827

LeetCode 827 Making A Large Island - Logic

DSU + Virtual Flip

Pattern - Hub Nodes

Reducing Edges

Codeforces 1263D Secret Passwords - Problem Statement

Codeforces 1263D

Codeforces 1263D Secret Passwords - Logic

Letters are Hubs

Pattern - Offline Queries

Reordering Time

Quiz: Offline Processing

Knowledge check

LeetCode 1697 Edge Limited Paths - Problem Statement

LeetCode 1697

LeetCode 1697 Edge Limited Paths - Implementation Plan

Sorting Everything

Pattern - The Reverse Time Trick

Destruction is hard

USACO 644 Closing the Farm - Problem Statement

USACO Gold

USACO 644 Closing the Farm - Solution

Adding Barns

Quiz: Reverse Time Trick

Knowledge check

Section Recap

Dynamic Connectivity

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████