{ }codelper

Learn › TypeScript

Algorithms · 32

Graphs and depth-first search

Write down who is connected to whom, then visit everything you can reach.

A graph is data made of points (people, towns, rooms) and the lines that join them (friendships, roads, doors).
The example below reads pairs of friends, builds a friend list for each person, then prints the order in which it reaches people by following friends from person 1, and the number of groups of people who can reach each other.

import { readFileSync } from "node:fs";const [[n, m], ...pairs]: number[][] = readFileSync(0, "utf8").trim().split("\n").map((l) => l.trim().split(/\s+/).map(Number));const adj: number[][] = Array.from({ length: n + 1 }, () => []); // adj[v] = v번의 친구들for (const [a, b] of pairs.slice(0, m)) {  adj[a].push(b); // 서로 친구라 양쪽에 넣어요  adj[b].push(a);} let seen: boolean[] = new Array<boolean>(n + 1).fill(false);const order: number[] = []; // 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요function dfs(v: number): void {  seen[v] = true;  order.push(v);  for (const w of adj[v]) {    if (!seen[w]) dfs(w);  }} dfs(1);console.log(order.join(" ")); // 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나seen = new Array<boolean>(n + 1).fill(false);let groups: number = 0;for (let s = 1; s <= n; s++) {  if (seen[s]) continue;  groups++;  seen[s] = true;  const stack: number[] = [s];  while (stack.length > 0) {    const v = stack.pop()!;    for (const w of adj[v]) {      if (!seen[w]) {        seen[w] = true;        stack.push(w);      }    }  }}console.log(groups);
stdin
7 5
1 2
1 3
2 4
3 4
5 6
stdout
1 2 4 3
3

Key points

  • The input usually comes as pairs "a b".
    Turn them into a list of neighbours for each person, adj[v] (an adjacency list).
    Then you know who v's neighbours are at once, without scanning the pairs again.
    If the link goes both ways, put b in adj[a] and a in adj[b].
  • If the numbers start at 1, make n + 1 slots and leave slot 0 unused.
    Then a number is its own index.
  • Depth-first search (DFS) puts a visited mark (seen) on where it is, and as soon as it meets a neighbour it has not visited, it goes in there.
    When there is nowhere left to go, it comes back and looks at the remaining neighbours.
    The example's dfs(v) takes only the number v; adj, seen and order are kept outside the function and shared.
    In the example, person 1's friends are 2 and 3, but having entered 2 it goes on to 4 before it ever looks at 3, so the order is 1 2 4 3.
  • Because of the mark, each person is entered only once and each friendship is looked at once from each side.
    So the amount of work is the number of people plus the number of pairs.
  • Instead of recursion you can keep a stack yourself.
    Push the start, then repeat until the stack is empty: pop one, and mark and push its unvisited neighbours.
    The visiting order may differ (the example gives 1 3 4 2 with a stack), but the people reached are the same.
  • Every time a search has to start again from a person with no mark, that is one more group.
    The example has {1, 2, 3, 4}, {5, 6} and {7}, so 3.

How each language writes it

Pythonadj = [[] for _ in range(n + 1)], adj[a].append(b).
A stack is a list with append and pop()
JavaScriptArray.from({ length: n + 1 }, () => []), adj[a].push(b).
A stack is an array with push and pop()
TypeScriptSame as JavaScript.
The type is number[][].
stack.pop() has type number | undefined, so where you have checked the stack is not empty, write stack.pop()!
Javaadd n + 1 empty ArrayLists to an ArrayList<ArrayList<Integer>>, then adj.get(a).add(b).
A stack is an ArrayDeque with push and pop
C#Every slot of new List<int>[n + 1] is null, so put a new List<int>() in each one.
Then adj[a].Add(b).
A stack is Stack<int> with Push and Pop
C++std::vector<std::vector<int>> adj(n + 1) — this makes n + 1 separate empty vectors.
adj[a].push_back(b).
Use a vector as a stack with push_back, back() and pop_back()
CThere is no list that grows.
Keep int adj[MAX][MAX] and a neighbour count deg[v], and add with adj[a][deg[a]++] = b.
The stack is also an array plus a top index
CraykonNewList(n + 1, []) makes a separate empty list in every slot.
adj[a].Add(b); walk the neighbours with foreach (w in adj[v]).
Use the end of a list as a stack: push with stack.Add(w), read stack[stack.Count - 1], then remove it with stack.RemoveAt(stack.Count - 1)

Common mistakes

Making the neighbour lists with [[]] * nPython · JavaScript · TypeScript

adj = [[]] * 3
adj[1].append(2)
print(adj)

→ [[2], [2], [2]] — all three slots point at one empty list, so a friend added to person 1 shows up for everyone. JavaScript's new Array(3).fill([]) does the same

Make a new list for each slot: [[] for _ in range(n + 1)], Array.from({ length: n + 1 }, () => []).

Leaving out the visited mark

void dfs(int v) {
    order.push_back(v);
    for (int w : adj[v]) dfs(w);
}

→ If 1 and 2 are friends, it goes 1 → 2 → 1 → 2 … without end until the stack overflows and the program dies with SIGSEGV. With the same mistake Python stops with RecursionError, JavaScript with RangeError, Java with StackOverflowError, C# prints Stack overflow. and dies, and Craykon stops with "functions were called too deeply"

Set seen[v] = true as soon as you enter, and only go into neighbours that have no mark.

Creating the array but not the lists inside itJava · C#

List<int>[] adj = new List<int>[3];
adj[1].Add(2);

→ NullReferenceException — a new array has null in every slot. In Java, an array made with new ArrayList[3] stops with NullPointerException in the same way

Before using it, loop over the slots and store adj[v] = new List<int>(); in each (new ArrayList<>() in Java).

How languages differ
Recursive DFS is short, but when people are joined in one long line it goes that many levels deep.
On the judge, the example's Python code solves an input with 900 people in a line but stops with RecursionError at 1,100, and the Craykon code solves 1,100 but stops at 5,000.
If n can go beyond a few thousand, write it with a stack from the start.

Practice

  1. Following the crossroad notes8P0380
  2. The seeker's walk in hide-and-seek8P0377
  3. Friend groups8P0118
  4. Line numbers in a folded reply thread8P0292
  5. The person with the most friends in common8P0293
  6. Rebuild only the stale files8P0326
  7. Exploring a cave by feel, picking up keys8P0190
  8. Slack time of festival tasks8P0303