Introduction

Graph traversal algorithms visit all nodes within a graph in a certain order and can compute some information along the way. Two common algorithms for doing this are depth first search (DFS) and breadth first search (BFS).

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.

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.

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.

When implementing DFS, we often use a recursive function to visit the vertices and an array to store whether we've seen a vertex before.

Copy
import sys

sys.setrecursionlimit(10**5)  # Python has a default recursion limit of 1000

n = 6
visited = [False] * n

"""
Define adjacency list and read in problem-specific input here.

BFS

In a breadth-first search, we travel through the vertices in order of their distance from the starting vertex.

Prerequisite - Queues & Deques

Queues

A queue is a First In First Out (FIFO) data structure that supports three operations, all in $\mathcal{O}(1)$ time.

Copy
from queue import Queue

q = Queue()  # []
q.put(1)  # [1]
q.put(2)  # [1, 2]
v = q.queue[0]  # v = 1, q = [1, 2]
v = q.get()  # v = 1, q = [2]
v = q.get()  # v = 2, q = []
v = q.get()  # Code waits forever, creating TLE error.

Deques

A deque (usually pronounced "deck") stands for double ended queue and is a combination of a stack and a queue, in that it supports $\mathcal{O}(1)$ insertions and deletions from both the front and the back of the deque. Not very common in Bronze / Silver.

Copy
d = collections.deque()
d.appendleft(3)  # [3]
d.appendleft(4)  # [4, 3]
d.append(7)  # [4, 3, 7]
d.popleft()  # [3, 7]
d.appendleft(1)  # [1, 3, 7]
d.pop()  # [1, 3]

Implementation

When implementing BFS, we often use a queue to track the next vertex to visit. Like DFS, we'll also keep an array to store whether we've seen a vertex before.

Copy
from collections import deque

"""
Define adjacency list and read in problem-specific input

In this example, we've provided "dummy input" that's
reflected in the GIF above to help illustrate the
order of the recursive calls.
"""

Solution - Building Roads

Note that each edge decreases the number of connected components by either zero or one. So you must add at least $C-1$ edges, where $C$ is the number of connected components in the input graph.

To compute $C$, iterate through each node. If it has not been visited, visit it and all other nodes in its connected component using DFS or BFS. Then $C$ equals the number of times we perform the visiting operation.

There are many valid ways to pick $C-1$ new roads to build. One way is to choose a single representative from each of the $C$ components and link them together in a line.

DFS Solution

Copy
from collections import deque

n, m = map(int, input().split())

adj = [[] for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)

An Issue With Deep Recursion

If you run the solution code locally on the line graph generated by the following Python code:

Copy
n = 100000
print(n, n - 1)
for i in range(1, n):
	print(i, i + 1)

Traceback (most recent call last):
  File "input/code.py", line 28, in <module>
	solve(n, adj)
  File "input/code.py", line 14, in solve
	dfs(start, start)
  File "input/code.py", line 9, in dfs
	dfs(start, next)
  File "input/code.py", line 9, in dfs
	dfs(start, next)
  File "input/code.py", line 9, in dfs
	dfs(start, next)
  [Previous line repeated 994 more times]
  File "input/code.py", line 7, in dfs
	if next in unvisited:
RecursionError: maximum recursion depth exceeded in comparison

BFS Solution

Copy
from collections import deque

n, m = map(int, input().split())

adj = [[] for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)

Connected Component Problems

Solution - Building Teams

For each connected component, we can arbitrarily label a node and then run DFS or BFS. 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.

DFS Solution

Copy
import sys

input = sys.stdin.readline

sys.setrecursionlimit(int(1e9))  # disable recursion limit

n, m = map(int, input().strip().split())
adj = [[] for _ in range(n)]
team = [0] * n  # 0: not assigned yet, 1: team 1, 2: team 2

BFS Solution

The specifics of the algorithm are almost exactly the same; it's just that we do them in an iterative rather than recursive fashion.

Copy
from collections import deque

n, m = map(int, input().split())

adj = [[] for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)

Graph Two-Coloring Problems

Quiz