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 builtin queue 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
import java.util.*;

public class Main {
	public static void main(String[] args) {
		int n = 6;
		boolean[] visited = new boolean[n];
		List<Integer>[] adj = new ArrayList[6];
		for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); }
		adj[0] = new ArrayList<>(Arrays.asList(1, 2, 4));
		adj[1] = new ArrayList<>(Arrays.asList(3, 4));

C++

Copy
#include <queue>
#include <vector>

using std::queue;
using std::vector;

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

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 <deque>
#include <iostream>
#include <vector>

using namespace std;

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

void dfs(int node) {

Java

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

public class BuildingRoads {
	static List<Integer>[] adj;
	static boolean[] visited;

	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int n = io.nextInt();

Python

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)

However, this code causes a runtime error on nearly half the test cases. What could be going wrong?

C++

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

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

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 with sys.setrecursionlimit(10 ** 6), although we still get TLE on two test cases. To resolve this, we can implement a BFS solution, as shown below.

C++

Copy
#include <deque>
#include <iostream>
#include <vector>

using namespace std;

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

Java

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

public class BuildingRoads {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int m = io.nextInt();

		List<Integer>[] adj = new ArrayList[n];

Python

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)

C++

Copy
#include <iostream>
#include <vector>

using namespace std;

vector<int> assigned;
vector<vector<int>> adj;

/** @return true only if it's possible to assign each person to a team */
bool dfs(int node) {

Java

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

public class BuildingTeams {
	static List<Integer>[] adj;
	static int[] assigned;

	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int n = io.nextInt();

C++

Copy
#include <deque>
#include <iostream>
#include <vector>

using namespace std;

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

Java

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

public class BuildingTeams {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int m = io.nextInt();

		List<Integer>[] adj = new ArrayList[n];

Python

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)