1
type AdjList = Map<number, number[]>;
2

3
function buildGraph(n: number, edges: number[][], directed = true): AdjList {
4
  const graph: AdjList = new Map();
5

6
  for (let i = 0; i < n; i++) {
7
    graph.set(i, []);
8
  }
9

10
  for (const [from, to] of edges) {
11
    graph.get(from)!.push(to);
12
    if (!directed) graph.get(to)!.push(from);
13
  }
14

15
  return graph;
16
}

1
function dfs(graph: AdjList, start: number): number[] {
2
  const visited = new Set<number>();
3
  const result: number[] = [];
4

5
  function visit(node: number): void {
6
    if (visited.has(node)) return;
7
    visited.add(node);
8
    result.push(node);
9

10
    for (const next of graph.get(node) ?? []) {
11
      visit(next);
12
    }
13
  }
14

15
  visit(start);
16
  return result;
17
}

1
function bfs(graph: AdjList, start: number): number[] {
2
  const queue = [start];
3
  const visited = new Set<number>([start]);
4
  const result: number[] = [];
5
  let head = 0;
6

7
  while (head < queue.length) {
8
    const node = queue[head++];
9
    result.push(node);
10

11
    for (const next of graph.get(node) ?? []) {
12
      if (visited.has(next)) continue;
13
      visited.add(next);
14
      queue.push(next);
15
    }
16
  }
17

18
  return result;
19
}

1
function topologicalSort(numCourses: number, prerequisites: number[][]): number[] {
2
  const graph = buildGraph(numCourses, prerequisites);
3
  const indegree = new Array(numCourses).fill(0);
4

5
  for (const [, to] of prerequisites) {
6
    indegree[to]++;
7
  }
8

9
  const queue: number[] = [];
10
  for (let i = 0; i < numCourses; i++) {
11
    if (indegree[i] === 0) queue.push(i);
12
  }
13

14
  const result: number[] = [];
15
  let head = 0;
16

17
  while (head < queue.length) {
18
    const node = queue[head++];
19
    result.push(node);
20

21
    for (const next of graph.get(node) ?? []) {
22
      indegree[next]--;
23
      if (indegree[next] === 0) queue.push(next);
24
    }
25
  }
26

27
  return result.length === numCourses ? result : [];
28
}

1
function findCircleNum(isConnected: number[][]): number {
2
  const n = isConnected.length;
3
  const visited = new Set<number>();
4
  let provinces = 0;
5

6
  function dfsCity(city: number): void {
7
    visited.add(city);
8

9
    for (let next = 0; next < n; next++) {
10
      if (isConnected[city][next] === 1 && !visited.has(next)) {
11
        dfsCity(next);
12
      }
13
    }
14
  }
15

16
  for (let city = 0; city < n; city++) {
17
    if (!visited.has(city)) {
18
      provinces++;
19
      dfsCity(city);
20
    }
21
  }
22

23
  return provinces;
24
}