# Depth First Search (DFS)

Authors: Siyong Huang, Andrew Wang, Jason Chen, Benjamin Qi

Recursively traversing a graph.

Resources | |||
---|---|---|---|

CSA | up to but not including "More about DFS" | ||

CPH | example diagram + code |

From the second resource:

Depth-first search (DFS) is a straightforward graph traversal technique. The algorithm begins at a starting node, and proceeds to all other nodes that are reachable from the starting node using the edges of the graph.

Depth-first search always follows a single path in the graph as long as it finds new nodes. After this, it returns to previous nodes and begins to explore other parts of the graph. The algorithm keeps track of visited nodes, so that it processes each node only once.

## Application - Connected Components

Focus Problem – read through this problem before continuing!

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.

In the above focus problem, the goal is to add the minimum possible number of edges such that the entire graph forms 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 | |||||
---|---|---|---|---|---|---|---|---|---|

Silver | Easy | ## Show TagsConnected Components | |||||||

Silver | Easy | ## Show TagsDirected Graph | |||||||

Silver | Easy | ## Show TagsConnected Components | |||||||

Kattis | Easy | ## Show TagsConnected Components | |||||||

CSES | Normal | ## Show TagsDirected Graph | |||||||

Gold | Normal | ## Show TagsBinary Search, Connected Components | |||||||

Silver | Normal | ## Show TagsBinary Search, Connected Components | |||||||

Kattis | Very Hard | ## Show TagsBinary Search, Connected Components | |||||||

## Application - Graph Two-Coloring

Focus Problem – read through this problem before continuing!

**Graph two-coloring** refers to assigning a boolean value to each node of the
graph, dictated by the edge configuration. The most common example of a
two-colored graph is a **bipartite graph**, in which each edge connects two
nodes of opposite colors.

In the above focus problem, the goal is to assign each node (friend) of the graph to one of two colors (teams), subject to the constraint that edges (friendships) connect two nodes of opposite colors. In other words, we need to check whether the input is a bipartite graph and output a valid coloring if it is.

### Solution - Building Teams

Resources | |||
---|---|---|---|

CPH | Brief solution sketch with diagrams. |

The idea is that we can arbitrarily label a node and then run DFS. Every time we visit a new (unvisited) node, we set its color based on the edge rule. When we visit a previously visited node, check to see whether its color matches the edge rule.

C++

#include <cstdio>#include <vector>const int MN = 1e5+10;int N, M;bool bad, vis[MN], group[MN];std::vector<int> a[MN];void dfs(int n=1, bool g=0)

Java

### Warning!

Because Java is so slow, an adjacency list using lists/arraylists results in TLE. Instead, the Java sample code uses the edge representation mentioned in the optional block above.

import java.io.*;import java.util.*;public class BuildingTeams{static InputReader in = new InputReader(System.in);static PrintWriter out = new PrintWriter(System.out);public static final int MN = 100010;public static final int MM = 200010;

### Problems

Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|

CF | Easy | ## Show TagsBipartite | |||||||

Silver | Easy | ## Show TagsBipartite | |||||||

Baltic OI | Hard | ## Show TagsDFS, Median | |||||||

APIO | Very Hard | ## Show TagsBipartite | |||||||

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