Interview Bootcamp
Vote

0% completed

​

Problem 2: Number of Provinces (medium)

Problem Statement

Imagine a country with several cities. Some cities have direct roads connecting them, while others might be connected through a sequence of intermediary cities. Using a matrix representation, if matrix[i][j] holds the value 1, it indicates that city i is directly linked to city j and vice versa. If it holds 0, then there's no direct link between them.

Determine the number of separate city clusters (or provinces).

.....

.....

.....

Like the course? Get enrolled and start learning!
F

Foo Bar

· 3 years ago

I understand that each DFS has O(N) time complexity and we call DFS for each node. That being said, we only run DFS if the node is not visited.

For example, let's say we have 6 cities indexed 0 through 5. City 0 through 3 are connected (i.e., they form a province) and city 4 and 5 are connected (i.e., they form another province). The algorithm runs DFS on city 0 but skips the DFS call for city 1, 2, and 3 since they will have already been visited. The algorithm will then make a DFS call for city 4 and skip the DFS call for city 5. Therefore, we will never call DFS for every node in the graph, it will be called enough times to visit each node once (O(n)). Am I misunderstanding?

Show 1 reply
T

Thai Minh

· 2 years ago

from collections import defaultdict, deque
class Solution:
    def findCircleNum(self, isConnected) -> int:
        provinces = 0
        # ToDo: Write Your Code Here.
        # create a set visited to track node that already visited
        # this also used to track matrix adjacent node
        # we then loop through each node and check if it is not visited, we then run a bfs to go through that path
        # that we chase up until we done which also count as 1 province
        visited = [False] * len(isConnected)
        def bfs(city):
            stack = deque()
            stack.append(city)
            while stack:
                city = stack.popleft()
                for i in range(len(isConnected)):
                    if isConnected[city][i] == 1 and not visited[i]:
S

shekhart91

· 2 years ago

Ideally, when we see a matrix, the first thought that comes after doing island traversal, is applying that pattern, why wasn't a solution added based on that pattern?

Show 2 replies