Graph Traversal

C++

std::queue

• push: inserts at the back of the queue
• pop: deletes from the front of the queue
• front: retrieves the element at the front without removing it.

Copy
queue<int> q;
q.push(1);                  // [1]
q.push(3);                  // [3, 1]
q.push(4);                  // [4, 3, 1]
q.pop();                    // [4, 3]
cout << q.front() << endl;  // 3

Java

• add: insertion at the back of the queue
• poll: deletion from the front of the queue
• peek: which retrieves the element at the front without removing it

Java doesn't actually have a Queue class; it's only an interface. The most commonly used implementation is the LinkedList, declared as follows:

Copy
Queue<Integer> q = new LinkedList<Integer>();
q.add(1);                      // [1]
q.add(3);                      // [3, 1]
q.add(4);                      // [4, 3, 1]
q.poll();                      // [4, 3]
System.out.println(q.peek());  // 3

Python

Python has a queue built-in module.

• Queue.put(n): Inserts element to the back of the queue.
• Queue.get(): Gets and removes the front element. If the queue is empty, this will wait forever, creating a TLE error.
• Queue.queue[n]: Gets the nth element without removing it. Set n to 0 for the first element.

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.

C++

std::deque

The four methods for adding and removing are push_back, pop_back, push_front, and pop_front.

Copy
deque<int> d;
d.push_front(3);  // [3]
d.push_front(4);  // [4, 3]
d.push_back(7);   // [4, 3, 7]
d.pop_front();    // [3, 7]
d.push_front(1);  // [1, 3, 7]
d.pop_back();     // [1, 3]

You can also access deques in constant time like an array in constant time with the [] operator. For example, to access the element $\texttt{i}$ for some deque $\texttt{dq}$, do $\texttt{dq[i]}$.

Java

In Java, the deque class is called ArrayDeque. The four methods for adding and removing are addFirst , removeFirst, addLast, and removeLast.

Copy
ArrayDeque<Integer> deque = new ArrayDeque<Integer>();
deque.addFirst(3);    // [3]
deque.addFirst(4);    // [4, 3]
deque.addLast(7);     // [4, 3, 7]
deque.removeFirst();  // [3, 7]
deque.addFirst(1);    // [1, 3, 7]
deque.removeLast();   // [1, 3]

Python

In Python, collections.deque() is used for a deque data structure. The four methods for adding and removing are appendleft, popleft, append, and pop.

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]

C++

Copy
#include <cstdio>
#include <vector>

const int MN = 1e5 + 10;

int N, M, ans, rep[MN];
std::vector<int> adj_list[MN];
bool visited[MN];

void dfs(int node) {

Java

Copy
import java.io.*;
import java.util.*;

public class Main {
	public static ArrayList<Integer> adj[];
	public static ArrayList<Integer> rep = new ArrayList<Integer>();
	public static boolean visited[];
	public static void main(String[] args) throws IOException {
		BufferedReader br =
		    new BufferedReader(new InputStreamReader(System.in));

Python

Copy
def solve(n, adj):
	unvisited = set(range(1, n + 1))
	starts = set()

	def dfs(current):
		for next in adj[current]:
			if next in unvisited:
				unvisited.remove(next)
				dfs(next)

Unfortunately, a danger in using DFS when dealing with large bounds is the possibility of a RecursionError. This commonly occurs for $N>10^3$ since the recursion limit in Python is set to 1000 by default. So if you submit the above code, you'll get the following:

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

We can fix this by increasing the recursion limit:

Copy
import sys

sys.setrecursionlimit(1000000)

although we still get TLE on two test cases.

To resolve this, we can implement a non-recursive solution (which turns out to be slightly faster). You can imagine adding to to_visit as calling the function recursively and popping from to_visit as starting the execution of the recursive function (though they are not exactly equivalent in the strictest sense).

Copy
def solve(n, adj):
	unvisited = set(range(1, n + 1))
	starts = set()

	def dfs(start):
		to_visit = [start]
		while to_visit:
			current = to_visit.pop()
			for next in adj[current]:
				if next in unvisited:

Recursion errors also come up frequently in flood fill problems.

C++

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) {

Java

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;