Number Of Connected Components In An Undirected Graph Leetcode 323 [Python]
In this guide, we will tackle the LeetCode problem "Number of Connected Components In An Undirected Graph," which falls under the category of Graphs.
This is a medium difficulty problem that requires you to find the number of connected components in an undirected graph.
We will explore the problem, understand its constraints, discuss two different approaches to solving it, and provide Python code solutions.
Let's dive in.
Problem Overview
Problem Statement:
You are given an undirected graph with n nodes and an array of edges.
Each element in the edges array is a pair [a, b], which signifies an edge between node a and node b in the graph.
Your task is to determine the number of connected components in the given graph.
Example:
Let's look at a couple of examples to understand the problem better:
Example 1:
Input:
n = 3
edges = [[0, 1], [0, 2]]
Output:
1
In this example, all three nodes (0, 1, and 2) are connected, forming a single connected component.
Example 2:
Input:
n = 6
edges = [[0, 1], [1, 2], [2, 3], [4, 5]]
Output:
2
In this case, we have two connected components.
The first component includes nodes 0, 1, 2, and 3, while the second component consists of nodes 4 and 5. Now that we have a clear understanding of the problem, let's dive deeper.
Understanding Constraints
Before we proceed with the solution, let's discuss the constraints of this problem:
- The number of nodes,
n, is a positive integer. - The
edgesarray consists of pairs[a, b]representing the edges, where0 <= a, b < n. - The graph is undirected, meaning that if there's an edge between node
aand nodeb, there's also an edge between nodeband nodea.
Efficient Approach with Union Find
To solve this problem efficiently, we can use a data structure called "Union Find" or "Disjoint Set Union" (DSU).
Union Find allows us to keep track of connected components in a graph efficiently.
We'll go through the process step by step.
Union Find Data Structure
First, let's set up the Union Find data structure.
We'll maintain two arrays: one to keep track of the parent of each node and another to store the rank (size) of each component.
class UnionFind:
def __init__(self):
self.parent = {} # Stores the parent of each node.
self.rank = {} # Stores the rank (size) of each component.
def find(self, x):
# Find the root parent of a node using path compression.
if self.parent.get(x, x) != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
# Union two components based on their rank.
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
if self.rank.get(root_x, 1) < self.rank.get(root_y, 1):
self.parent[root_x] = root_y
self.rank[root_y] = self.rank.get(root_y, 1) + self.rank.get(root_x, 1)
else:
self.parent[root_y] = root_x
self.rank[root_x] = self.rank.get(root_x, 1) + self.rank.get(root_y, 1)
Now that we have our Union Find data structure in place, let's implement the solution to the problem.
Python Code Solution
from typing import List
class Solution:
def countComponents(self, n: int, edges: List[List[int]) -> int:
# Initialize Union Find data structure.
dsu = UnionFind()
# Iterate through the edges and union the nodes.
for a, b in edges:
dsu.union(a, b)
# Create a set of unique root parents and return its size as the number of components.
return len(set(dsu.find(x) for x in range(n))
In this Python solution, we first create an instance of the Union Find data structure.
We then iterate through the edges and use the union method to merge nodes that belong to the same connected component.
After processing all edges, we count the number of unique root parents, which corresponds to the number of connected components, and return that count.
Reasoning Behind Our Efficient Approach
The Union Find approach is efficient for this problem because it allows us to perform operations in nearly constant time.
The find operation, which determines the root parent of a node, is optimized using path compression.
This optimization ensures that the tree structure formed by the Union Find data structure remains shallow, resulting in fast find and union operations.
Additionally, the rank-based union ensures that we always attach the smaller component to the larger one, which further helps in maintaining shallow tree structures.
Overall, Union Find is a powerful data structure for solving connectivity problems in graphs, making it an ideal choice for this LeetCode problem.
Related Interview Questions By Company:
Related Interview Questions By Difficulty:
Related Interview Questions By Category:
Conclusion
In this guide, we tackled the LeetCode problem Number Of Connected Components In An Undirected Graph We discussed the problem's overview, examined its constraints, and provided an efficient Python solution using the Union Find data structure.
Union Find allows us to determine the number of connected components in an undirected graph in an optimal manner.
We encourage you to try the solution on your own, experiment with different test cases, and deepen your understanding of Union Find.
If you found this guide helpful, please consider liking and subscribing for more content.
Feel free to comment, ask questions, make suggestions, and share this content to help others.
Happy coding!
Question Link: Number of Connected Components In An Undirected Graph – LeetCode
By following this guide, you can now efficiently solve the LeetCode problem Number Of Connected Components In An Undirected Graph using the Union Find data structure.
Understanding the problem, its constraints, and the reasoning behind the solution is essential for mastering such algorithmic challenges.
Feel free to use the provided Python solution as a reference, and don't hesitate to ask questions or share your insights.
Happy coding!
