Depth First Search (DFS)

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

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

Problems

Application - Graph Two-Coloring

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

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.

Copy
#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)

Copy
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