木とグラフ — 隣接リスト・DFS・BFSの使い分け

// N頂点、辺のリスト edges = [[0,1], [0,2], [1,3]] （無向）
const graph: number[][] = Array.from({ length: N }, () => []);
for (const [a, b] of edges) {
  graph[a].push(b);
  graph[b].push(a);   // 無向なら両方向に張る（有向ならこの行を消す）
}
// graph[0] → [1, 2]  … 頂点0の隣は1と2

function countGroups(N: number, graph: number[][]): number {
  const visited = new Array(N).fill(false);
 
  const dfs = (v: number) => {
    visited[v] = true;
    for (const next of graph[v]) {
      if (!visited[next]) dfs(next);   // 未訪問の隣へ潜る
    }
  };
 
  let groups = 0;
  for (let v = 0; v < N; v++) {
    if (!visited[v]) {
      groups++;        // 未訪問の頂点 = 新しいグループの発見
      dfs(v);          // そのグループ全体を訪問済みにする
    }
  }
  return groups;
}

const dfsIterative = (start: number) => {
  const stack = [start];
  visited[start] = true;
  while (stack.length > 0) {
    const v = stack.pop()!;
    for (const next of graph[v]) {
      if (!visited[next]) {
        visited[next] = true;
        stack.push(next);
      }
    }
  }
};

function bfsDistances(N: number, graph: number[][], start: number): number[] {
  const dist = new Array(N).fill(-1);   // -1 = 未到達
  const queue: number[] = [start];
  let head = 0;
  dist[start] = 0;
 
  while (head < queue.length) {
    const v = queue[head++];
    for (const next of graph[v]) {
      if (dist[next] === -1) {          // distがvisited判定を兼ねる
        dist[next] = dist[v] + 1;
        queue.push(next);
      }
    }
  }
  return dist;
}

// 各頂点を根とする部分木のサイズを求める
const size = new Array(N).fill(0);
const dfs = (v: number, parent: number): number => {
  let s = 1;                            // 自分自身
  for (const c of graph[v]) {
    if (c !== parent) s += dfs(c, v);   // 子の部分木サイズを合算
  }
  return (size[v] = s);
};
dfs(0, -1);