1"""
2Connected Components - DFS-Based Approach
3
4Finds all connected components in an undirected graph using Depth-First Search.
5Each component is a maximal set of vertices where any two vertices are connected
6by a path.
7
8Key Insight:
9 Starting DFS from an unvisited vertex explores its entire component.
10 Repeat for all unvisited vertices to find all components.
11
12Time Complexity: O(V + E) - visits every vertex and edge once
13Space Complexity: O(V) - visited set + recursion stack
14
15Advantages:
16 - Simple and intuitive
17 - Easy to implement recursively or iteratively
18 - Works well with adjacency list representation
19 - Can easily track which vertices belong to which component
20
21Graph Representation:
22 Uses adjacency list format for UNDIRECTED graphs.
23 Format: {node: {neighbor1, neighbor2, ...}}
24"""
25
26from typing import Dict, Set, List, Any
27
28
29def find_components(graph: Dict[Any, Set[Any]]) -> List[Set[Any]]:
30 """
31 Find all connected components using DFS.
32
33 Args:
34 graph: Adjacency list for undirected graph {node: {neighbors}}
35
36 Returns:
37 List of sets, where each set contains vertices in one component
38 """
39 visited = set()
40 components = []
41
42 def _dfs(node: Any, component: Set[Any]) -> None:
43 visited.add(node)
44 component.add(node)
45
46 for neighbor in graph.get(node, set()):
47 if neighbor not in visited:
48 _dfs(neighbor, component)
49
50 for node in graph:
51 if node not in visited:
52 component: Set[Any] = set()
53 _dfs(node, component)
54 components.append(component)
55
56 return components
57
58
59def count_components(graph: Dict[Any, Set[Any]]) -> int:
60 """
61 Count the number of connected components.
62
63 Args:
64 graph: Adjacency list for undirected graph
65
66 Returns:
67 Number of connected components
68 """
69 return len(find_components(graph))
70
71
72def are_connected(graph: Dict[Any, Set[Any]], u: Any, v: Any) -> bool:
73 """
74 Check if two vertices are in the same connected component.
75
76 Args:
77 graph: Adjacency list for undirected graph
78 u: First vertex
79 v: Second vertex
80
81 Returns:
82 True if u and v are connected, False otherwise
83 """
84 if u not in graph or v not in graph:
85 return False
86
87 visited = set()
88
89 def _dfs(node: Any) -> bool:
90 if node == v:
91 return True
92 visited.add(node)
93
94 for neighbor in graph.get(node, set()):
95 if neighbor not in visited:
96 if _dfs(neighbor):
97 return True
98 return False
99
100 return _dfs(u)
101
102
103def get_component(graph: Dict[Any, Set[Any]], vertex: Any) -> Set[Any]:
104 """
105 Get the connected component containing a specific vertex.
106
107 Args:
108 graph: Adjacency list for undirected graph
109 vertex: The vertex to find the component for
110
111 Returns:
112 Set of all vertices in the same component as vertex
113 """
114 if vertex not in graph:
115 return set()
116
117 component: Set[Any] = set()
118 visited = set()
119
120 def _dfs(node: Any) -> None:
121 visited.add(node)
122 component.add(node)
123
124 for neighbor in graph.get(node, set()):
125 if neighbor not in visited:
126 _dfs(neighbor)
127
128 _dfs(vertex)
129 return component
130
131
132# Example usage and demonstration
133if __name__ == "__main__":
134 # Example graph with 3 connected components
135 #
136 # Component 1: Component 2: Component 3:
137 # A --- B D --- E G
138 # | | |
139 # C --- F H
140 #
141 example_graph = {
142 "A": {"B", "C"},
143 "B": {"A", "F"},
144 "C": {"A", "F"},
145 "F": {"B", "C"},
146 "D": {"E", "H"},
147 "E": {"D"},
148 "H": {"D"},
149 "G": set(), # Isolated vertex
150 }
151
152 print("Connected Components (DFS):", find_components(example_graph))
153 print("Number of Components:", count_components(example_graph))
154 print("A and F connected?", are_connected(example_graph, "A", "F"))
155 print("A and D connected?", are_connected(example_graph, "A", "D"))
156 print("Component containing A:", get_component(example_graph, "A"))
157