# 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

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 | ||||

Gold | Normal | ## Show TagsDFS, Binary Search | ||||

Silver | Normal | ## Show TagsDFS, Binary Search | ||||

Kattis | Very Hard | ## Show TagsDFS, Binary Search |

## DFS in Directed Graphs

### 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!

## Give Us Feedback on Depth First Search (DFS)!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.