Grokking Data Structures & Algorithms for Coding Interviews

0% completed

​

Solution: Number of Provinces

Problem Statement

There are n cities. Some of them are connected in a network. If City A is directly connected to City B, and City B is directly connected to City C, city A is indirectly connected to City C.

If a group of cities are connected directly or indirectly, they form a province.

Given an n x n matrix isConnected where isConnected[i][j] = 1 if the i<sup>th</sup> city and the j<sup>th</sup> city are directly connected, and isConnected[i][j] = 0 otherwise, determine the total number of provinces.

Examples

  • Example 1:
    • Input: isConnected =

.....

.....

.....

Like the course? Get enrolled and start learning!
C

c.avina05

· 2 years ago

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