Very Frequent
0/21

# Depth First Search (DFS)

Authors: Siyong Huang, Benjamin Qi

Contributors: Andrew Wang, Jason Chen

Recursively traversing a graph.

### Prerequisites

Resources
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 – try your best to solve 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

See here.

### Pro Tip

Some problems that can be solved with DFS, such as Comfortable Cows, may be more easily solved with a queue (described in the BFS module).

### Problems

StatusSourceProblem NameDifficultyTags
SilverEasy
Show TagsConnected Components
SilverEasy
SilverEasy
Show TagsConnected Components
KattisEasy
Show TagsConnected Components
DMOJEasy
Show TagsDFS
CSESNormal
GoldNormal
Show TagsBinary Search, Connected Components
SilverNormal
Show TagsBinary Search, Connected Components
SilverNormal
Show Tags2P, Binary Search, Connected Components
SilverNormal
Show TagsDFS
CFHard
Show TagsDFS, Sorted Set
KattisVery Hard
Show TagsBinary Search, Connected Components
SilverVery Hard
Show TagsConstructive, Cycles, Spanning Tree

## Application - Graph Two-Coloring

Focus Problem – try your best to solve 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

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsBipartite
SilverEasy
Show TagsBipartite
CFEasy
Show TagsBipartite
Baltic OIHard
Show TagsDFS, Median
CCHard
Show TagsBipartite, DFS
APIOVery Hard
Show TagsBipartite

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