Back to course home
0% completed
Vote For New Content
A DFS Solution
c.avina05
Dec 30, 2024
It's silly to hop into Union-Find at this level if you haven't been exposed to it.
Here is a simple DFS solution.
class Solution: def findProvinces(self, isConnected): def dfs(node): visited[node] = True for neighbor in range(n): if isConnected[node][neighbor] == 1 and not visited[neighbor]: dfs(neighbor) provinces = 0 n = len(isConnected) visited = [False]*n for i in range(n): if not visited[i]: dfs(i) provinces += 1 return provinces
5
0
Comments
Comments
Design Gurus10 months ago
The DFS solution is presented as an alternate solution at the end of the lesson.
R
Russell Rogers6 months ago
This is the simplest solution and should have been presented first over the union find solution. The UF solution seems way too complicated for this.
On this page