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.