PrevNext
Very Frequent
 0/14

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

StatusSourceProblem NameDifficultyTags
SilverEasy
Show TagsConnected Components
SilverEasy
Show TagsDirected Graph
SilverEasy
Show TagsConnected Components
KattisEasy
Show TagsConnected Components
CSESNormal
Show TagsDirected Graph
GoldNormal
Show TagsBinary Search, Connected Components
SilverNormal
Show TagsBinary Search, Connected Components
KattisVery 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

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsBipartite
SilverEasy
Show TagsBipartite
Baltic OIHard
Show TagsDFS, Median
APIOVery 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!

PrevNext