Very Frequent
0/13
Depth First Search (DFS)
Authors: Siyong Huang, Andrew Wang, Jason Chen, Benjamin Qi
Recursively traversing a graph.
DFS in Undirected Graphs
| Resources | |||
|---|---|---|---|
| CSA | up to but not including "More about DFS" | ||
| CPH | example diagram + code | ||
A connected component is a maximal set of connected nodes in an undirected graph. In other words, two nodes are in the same connected component if and only if they can reach each other via edges in the graph.
Focus Problem – read through this problem before continuing!
For example, the goal of this problem above is to add edges such that the entire graph is a single connected component.
Solution - Building Roads
Solution
Optional: Adjacency List Without an Array of Vectors
See here.
Problems
| Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
|---|---|---|---|---|---|---|
| Silver | Easy | Show TagsDFS | External Sol | |||
| Silver | Easy | Show TagsDFS | ||||
| Silver | Easy | Show TagsDFS | External Sol | |||
| Silver | Easy | Show TagsTree, DFS | ||||
| Kattis | Easy | Show TagsDFS | ||||
| Silver | Normal | Show TagsSorting | External Sol | |||
| Gold | Normal | Show TagsDFS, Binary Search | ||||
| Silver | Normal | Show TagsDFS, Binary Search | ||||
| Kattis | Very Hard | Show TagsDFS, Binary Search |
DFS in Directed Graphs
| Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
|---|---|---|---|---|---|---|
| CSES | Easy | |||||
| CCO | Normal | |||||
| Silver | Hard | External Sol |
Module Progress:
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!