Skip to content

Graphs -> BFS And DFS

Traversal for reachability, layering, components, bipartiteness, and DFS-tree structure.

  • Topic slug: graphs/bfs-dfs
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 2
  • Repo companion pages: 0
  • Curated external problems: 7

Microtopics

  • reachability
  • connected-components
  • layering
  • dfs-tree
  • cycle-detection
  • bipartite-check

Learning Sources

Source Type
MIT 6.006 notes page Course
cp-algorithms BFS Reference
USACO Guide graph traversal Reference

Practice Sources

Source Type
CSES Problem Set Practice
USACO contest archive Practice
IOI tasks archive Practice

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Monsters CSES Medium Multi-Source BFS, Grid BFS Two-Phase BFS; Distance Grid; Path Reconstruction Queue BFS; Distance Arrays; Grid Moves Grid; Timing Classic BFS timing problem where monster arrival times reshape the reachable state space.

BFS Shortest Path

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Labyrinth CSES Easy Grid BFS Tree; Parent Array; Route Recovery Queue BFS; Parent Pointers; 4-Direction Moves Shortest Path; Path Reconstruction; Maze A clean way to practice BFS plus path reconstruction on an unweighted graph.

Bipartite Check

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Building Teams CSES Easy Bipartite DFS Coloring; Conflict Detection; Component Handling Graph Traversal; Parity Coloring; Visited States Two-Coloring; Bipartite Graph A canonical traversal problem that turns friendship constraints into bipartite checking.

Connected Components

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Counting Rooms CSES Easy Grid DFS Flood Fill; Component Sweep; Boundary Checks DFS; Visited Array; Grid Traversal Flood Fill; Components; Visited Cells A textbook first traversal problem with no extra graph tricks.

Directed Cycle

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Round Trip II CSES Medium Directed Graphs DFS State Colors; Stack-Based Recovery; Cycle Witness Directed DFS; Back-Edge Detection; Parent Pointers Directed Cycle; Recursion Stack; Witness Path; Topological Intuition; Reconstruction The directed counterpart to Round Trip, with trickier cycle recovery.

Undirected Cycle

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Round Trip CSES Medium Cycles DFS Parent Tracking; Cycle Reconstruction; Component Scan DFS; Parent Pointers; Recursion Stack Undirected Cycle; Back Edge; Witness Path; Cycle Detection; Undirected Graph; Reconstruction Great practice for detecting and reconstructing a cycle in an undirected graph.

Unweighted BFS

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Message Route CSES Easy Paths Layered BFS; Parent Tracking; Shortest Route Recovery BFS; Adjacency Lists; Backtracking Unweighted Shortest Path; Path Reconstruction; Network; Shortest Path The standard shortest-path-in-an-unweighted-graph template.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
COUNTINGROOMS Counting Rooms secondary easy grid graph modeling; iterative flood fill; connected components Note Code
MESSAGEROUTE Message Route primary easy breadth-first search; unweighted shortest path; parent reconstruction Note Code

Regeneration

python3 scripts/generate_problem_catalog.py