Here’s a solution to the “Connected Components in an Undirected Graph” problem:

from typing import List, Dict

def count_connected_components(graph: Dict[int, List[int]]) -> int:
    # Set to keep track of visited vertices
    visited = set()

    def dfs(vertex):
        # Mark the current vertex as visited
        visited.add(vertex)
        
        # Recursively visit neighbors
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor)

    # Initialize the count of connected components
    components_count = 0

    # Iterate through vertices in the graph
    for vertex in graph:
        if vertex not in visited:
            # If the vertex is not visited, start DFS from it
            dfs(vertex)
            components_count += 1

    return components_count

# Example usage:
graph1 = {0: [1, 2], 1: [0], 2: [0], 3: [4], 4: [3], 5: [6], 6: [5]}
result1 = count_connected_components(graph1)
print(result1)
assert result1 == 3
# Explanation: The graph has three connected components: {0, 1, 2}, {3, 4} and {5, 6}.

graph2 = {0: [1, 2], 1: [0], 2: [0], 3: [4, 5], 4: [3], 5: [3]}
result2 = count_connected_components(graph2)
print(result2)
assert result2 == 2
# Explanation: The graph has two connected components: {0, 1, 2} and {3, 4, 5}.

graph3 = {0: [1, 2], 1: [0], 2: [0], 3: [], 4: [5], 5: [4]}
result3 = count_connected_components(graph3)
print(result3)
assert result3 == 3
# Explanation: The graph has three connected components: {0, 1, 2}, {3}, and {4, 5}.

Time Complexity:

The time complexity of the solution is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because the algorithm uses a Depth-First Search (DFS) traversal, which visits each vertex and each edge once.

  • The outer for loop iterates through each vertex in the graph, contributing O(V).
  • The dfs function, when called, explores all neighbors of the current vertex, contributing O(E) in total across all vertices.

Therefore, the overall time complexity is determined by the sum of the number of vertices and the number of edges in the graph, making it O(V + E).

Space Complexity:

The space complexity is O(V), where V is the number of vertices. This is due to the space used for the set of visited vertices during the DFS traversal. The recursive stack space is also considered, but in the worst case, it is proportional to the depth of the recursion, which is at most V.