Number of Provinces — LeetCode 547 Python Solution
MediumDepth-First SearchBreadth-First SearchUnion FindGraph
- Problem
- #547
- Pattern
- Union-Find
- Reading time
- 3 min
- Source
- leetcode.com
The problem
There are n cities. Some of them are connected, while some are not.
Example
- Input
- isConnected = [[1,1,0],[1,1,0],[0,0,1]]
- Output
- 2
Python solution
Python
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
def dfs(i: int):
vis[i] = True
for j, x in enumerate(isConnected[i]):
if not vis[j] and x:
dfs(j)
n = len(isConnected)
vis = [False] * n
ans = 0
for i in range(n):
if not vis[i]:
dfs(i)
ans += 1
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n^2) |
| Space | O(n) auxiliary |
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 547. Number of Provinces 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
On a study list
This problem is on LeetCode 75.
Frequently asked questions
- How hard is LeetCode 547. Number of Provinces?
- LeetCode 547. Number of Provinces is rated Medium on LeetCode.
- What is the time complexity of LeetCode 547. Number of Provinces?
- The Python solution on this page runs in O(n^2).
- What is the space complexity of LeetCode 547. Number of Provinces?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 547. Number of Provinces cover?
- LeetCode 547. Number of Provinces is tagged Depth-First Search, Breadth-First Search, Union Find and Graph on LeetCode.