Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
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 Gurus
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