graphIsTree

/**
 * @param {number} num
 * @param {Array<[number, number]>} edges
 * @return {boolean}
 */
/**
 * A tree with n nodes must have exactly n - 1 edges.
Then I only need to verify connectivity.
If all nodes are reachable from node 0, the graph is connected.
Since it has exactly n - 1 edges and is connected, it must be acyclic.
 */
// Time: O(V + E), Space: O(V + E)
export default function graphIsTree(num, edges) {
  // A valid tree with n nodes must have exactly n - 1 edges.
  // This catches both:
  // - too few edges: disconnected graph
  // - too many edges: cycle must exist
  if (edges.length !== num - 1) {
    return false;
  }

  // Build adjacency list.
  const graph = Array.from({ length: num }, () => []);

  for (const [a, b] of edges) {
    graph[a].push(b);
    graph[b].push(a);
  }

  const visited = new Set();

  function dfs(node) {
    if (visited.has(node)) {
      return;
    }

    visited.add(node);

    for (const neighbor of graph[node]) {
      dfs(neighbor);
    }
  }

  // Start from node 0 and see if we can visit every node.
  dfs(0);

  return visited.size === num;
}