MediumNo. 0323LeetCode Premium
Number of Connected Components in an Undirected Graph — LeetCode 323 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Breadth-First Search, Union Find, Graph
- On study lists
- Blind 75 and NeetCode 150
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.
Example
- Input
- n = 5, edges = [[0,1],[1,2],[3,4]]
- Output
- 2
Python solution
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
def dfs(i: int) -> int:
if i in vis:
return 0
vis.add(i)
for j in g[i]:
dfs(j)
return 1
g = [[] for _ in range(n)]
for a, b in edges:
g[a].append(b)
g[b].append(a)
vis = set()
return sum(dfs(i) for i in range(n))Complexity
- Time
- O(n + m)
- Space · auxiliary
- O(n + m)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 323. Number of Connected Components in an Undirected Graph is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0399 | Evaluate Division | Medium |
| 0547 | Number of Provinces | Medium |
| 0684 | Redundant Connection | Medium |
| 0685 | Redundant Connection II | Hard |
| 0785 | Is Graph Bipartite? | Medium |
| 0886 | Possible Bipartition | Medium |
Frequently asked questions
- How hard is LeetCode 323. Number of Connected Components in an Undirected Graph?
LeetCode 323. Number of Connected Components in an Undirected Graph is rated Medium on LeetCode.
- What is the time complexity of LeetCode 323. Number of Connected Components in an Undirected Graph?
The Python solution on this page runs in O(n + m).
- What is the space complexity of LeetCode 323. Number of Connected Components in an Undirected Graph?
The Python solution on this page uses O(n + m) auxiliary space.
- What topics does LeetCode 323. Number of Connected Components in an Undirected Graph cover?
LeetCode 323. Number of Connected Components in an Undirected Graph is tagged Depth-First Search, Breadth-First Search, Union Find and Graph on LeetCode.
- Is LeetCode 323. Number of Connected Components in an Undirected Graph a premium problem?
Yes. LeetCode 323. Number of Connected Components in an Undirected Graph is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.