Graph Traversal

C++

Copy
#include <bits/stdc++.h>
using namespace std;

int n = 6;
vector<vector<int>> adj(n);
vector<bool> visited(n);

void dfs(int current_node) {
	if (visited[current_node]) { return; }
	visited[current_node] = true;

Java

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

public class DFSDemo {
	static List<Integer>[] adj;
	static boolean[] visited;
	static int n = 6;

	public static void main(String[] args) throws IOException {
		visited = new boolean[n];

Python

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.

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 $i$th element of a 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]

Java

Copy
static final int MAX_N = (int)1e6;

public static void main(String[] args) throws IOException {
	boolean[] visited = new boolean[MAX_N];
	ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
	for (int i = 0; i < MAX_N; i++) adj.add(new ArrayList<Integer>());

	/*
	 * Define adjacency list and read in problem-specific input
	 *

C++

Copy
int n = 6;
vector<vector<int>> adj(n);
vector<bool> visited(n);

int main() {
	/*
	 * 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

Python

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 recrusive calls.
"""

C++

Copy
#include <iostream>
#include <vector>

using namespace std;

int N;
vector<vector<int>> adj;
vector<bool> visited;
vector<int> rep;

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)

However, this code causes a runtime error on five test cases. See the next subsection for how to fix this.

C++

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

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

then you might get a segmentation fault even though your code passes on the online judge. This occurs because every recursive call contributes to the size of the call stack, which is limited to a few megabytes by default. To increase the stack size, refer to this module. Short answer: If you would normally compile your code with g++ sol.cpp, then compile it with g++ -Wl,-stack_size,0xF0000000 sol.cpp instead.

Java

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

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

then you might get a StackOverflowError even though your code passes on the online judge. This occurs because every recursive call contributes to the size of the call stack, which is limited to less than a megabyte by default. To resolve this, you can pass an option of the form -Xss... to run the code with an increased stack size. For example, java -Xss512m Main will run the code with a stack size limit of 512 megabytes.

Python

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

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

then you will observe a RecursionError that looks like this:

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

This will occur for $N>10^3$ since the recursion limit in Python is set to 1000 by default. We can fix this by increasing the recursion limit:

Copy
import sys

sys.setrecursionlimit(1000000)

 Code Snippet: rest of solution (Click to expand)

although we still get TLE on two test cases. To resolve this, we can implement a BFS solution, as shown below.

C++

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;

	vector<vector<int>> adj(n);
	for (int i = 0; i < m; i++) {
		int u, v;

Python

Copy
from collections import deque

n, m = map(int, input().split())
adj = [[] for _ in range(n)]

for _ in range(m):
	u, v = map(int, input().split())

	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)

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;

C++

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n, m;
	cin >> n >> m;

	vector<vector<int>> adj(n);

Python

Copy
from collections import deque

n, m = map(int, input().split())
adj = [[] for i in range(n)]

for _ in range(m):
	u, v = map(int, input().split())

	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)