Number of Connected Components

  # ----------------------------------------
  # 1. Count Connected Components using DFS
  #
  # Input:
  #   n: number of nodes (ignored for letter-labeled graphs)
  #   edges: array of edges [u, v]
  # Output:
  #   Integer — number of connected components
  #
  # Time Complexity: O(N + E)
  # Space Complexity: O(N)
  # Example: count_components(nil, [['A', 'B'], ['A', 'C'], ['D', 'E']])
  # Output: 2 (components: {A, B, C}, {D, E})
  # ----------------------------------------
  def count_components(n_or_nil, edges)
    is_letters = edges.flatten.any? { |v| v.is_a?(String) }

    graph = Hash.new { |h, k| h[k] = [] }
    edges.each { |u, v| graph[u] << v; graph[v] << u }

    visited = {}
    count = 0

    dfs = lambda do |node|
      return if visited[node]
      puts "Visiting #{node}"
      visited[node] = true
      graph[node].each { |neighbor| dfs.call(neighbor) }
    end

    nodes = is_letters ? graph.keys : (0...n_or_nil).to_a

    nodes.each do |node|
      next if visited[node]
      puts "Starting DFS at #{node} (new component)"
      dfs.call(node)
      count += 1
    end

    puts "Total connected components: #{count}"
    count