Number of Connected Components in an Undirected Graph
The problem is about finding the number of connected components in an undirected graph with n
nodes and a given set of edges. A connected component is a set of vertices in a graph that are linked to each other by paths.
We can solve this problem using either DepthFirst Search (DFS) or UnionFind algorithm.
DepthFirst Search (DFS) Solution
Create Adjacency List: First, we need to represent the graph using an adjacency list. We can create a list of sets, where each set contains the nodes connected to a particular node.
DFS Function: Write a recursive DFS function that visits a node and all its connected nodes. Mark the visited nodes to avoid revisiting them.
Count Components: Iterate through all nodes. If a node is not visited yet, call the DFS function and increment the count of components.
Here’s the code:


The time complexity of this solution is O(n + e), where n is the number of nodes, and e is the number of edges. The space complexity is O(n + e).
UnionFind Solution
Initialize Parents: Create an array to represent the parent of each node, initially pointing to itself.
Find Function: Write a function to find the root (or parent) of a node.
Union Function: Write a function to connect two nodes (or sets), updating the parent accordingly.
Count Components: Iterate through the edges and perform union operations for each edge. Then, iterate through the parents array and count the unique roots.


The time complexity of the UnionFind solution is near O(n + e), and the space complexity is O(n).


Fill out the following sections:
Define the Interface Input: n (number of vertices), edges (undirected edges connecting vertices) Output: integer
Identify the Invariants
 n, edges
Identify the constraints
 Visit a node only once
Search the Problem Space
 Connected Components => Union Find
Classify the Problem Graph Traversal Union Find (datastructure)
Analyze the Examples _/
Solve the Problem by Hand
Describe the Pattern
Brute Force Approach
Analyze Time and Space Complexity
Time: O( ) Space: O( )
Outline the Solution
[0,1,2,3,4]
[t,t,t,f,f] visited
count = 1 start traversing from 0 [0,1,2,3,4]
count = 2 start traversing from 3
return count
Number of dfs calls we made is equal to the number of components counter = 0 Every time before we do


title: Number of Connected Components in an Undirected Graph excerpt: Given n nodes labeled from 0 to n  1 and a list of undirected edges, find the number of connected components in an undirected graph. tags: graphtraversal
Given n nodes labeled from 0 to n  1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.
Example 1:
Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]
0 3
 
1  2 4
Output: 2
Example 2:
Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
0 4
 
1  2  3
Output: 1
Note
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Thought Process
Define the Interface
Input: n (number of vertices), edges (undirected edges connecting vertices) Output: integer
Identify the Invariants
 n, edges
Identify the Constraints
 Visit a node only once
Search the Problem Space
 Connected Components => Union Find
Classify the Problem Graph Traversal Union Find (data structure)
Analyze the Examples Positive and negative cases.
Time and Space Complexity
Time: O(V+E) Space: O(V+E)
Solution Outline
[0,1,2,3,4]
[t,t,t,f,f] visited
count = 1 start traversing from 0 [0,1,2,3,4]
count = 2 start traversing from 3
return count
Number of dfs calls we made is equal to the number of components counter = 0 Every time before we do the traversal we increment the counter
[[0, 1], [1, 2], [3, 4]] 0 1 2

