547. Number of Provinces

Reformulated question¶

Given an undirected graph as an n x n adjacency matrix, return how many connected components it has.

Example:

isConnected = [
  [1,1,0],
  [1,1,0],
  [0,0,1],
]
-> 2  # {0,1}, {2}

Key trick¶

Treat each city as a graph node.

Start a DFS/BFS from every unvisited city.
Each new traversal discovers exactly one province.

Trap¶

Counting edges instead of connected components.
Forgetting a visited set/list, which causes double counting.
Assuming scanning only the upper triangle is enough for traversal logic.
Your DFS marks nodes as non-provinces too aggressively and can revisit nodes forever on dense graphs because it has no true visited guard.

Why this question is interesting¶

It is a basic graph connectivity problem disguised as a matrix problem.

It tests whether you can map matrix input to graph traversal.
It has multiple clean solutions: DFS, BFS, Union-Find.

Solve the problem with idiomatic python¶

class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n

        def dfs(city: int) -> None:
            # Visit all cities in the same connected component.
            visited[city] = True
            for nei in range(n):
                if isConnected[city][nei] == 1 and not visited[nei]:
                    dfs(nei)

        provinces = 0

        for city in range(n):
            # A new unvisited city starts a new province.
            if not visited[city]:
                provinces += 1
                dfs(city)

        return provinces

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("isConnected", "expected"),
    [
        ([[1]], 1),
        ([[1, 0], [0, 1]], 2),
        ([[1, 1], [1, 1]], 1),
        ([[1, 1, 0], [1, 1, 0], [0, 0, 1]], 2),
        ([[1, 0, 0], [0, 1, 0], [0, 0, 1]], 3),
        ([[1, 1, 0, 0], [1, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 1]], 2),
        ([[1, 1, 1], [1, 1, 1], [1, 1, 1]], 1),
    ],
)
def test_find_circle_num(isConnected, expected):
    assert Solution().findCircleNum(isConnected) == expected

Comment my solution¶

Your idea is aiming at component merging, but the implementation is not correct.

It does not maintain a real visited structure.
It starts outer loops from 1, so city 0 is never used as a starting point.
It only explores neighbors k > j, which can miss reachable nodes.
It can recurse repeatedly on already explored nodes.
province argument is unused.

A small counterexample:

[
  [1,1,1],
  [1,1,1],
  [1,1,1],
]

Expected: 1
Your code can keep recursing between nodes without a visited check.

class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        provinces = [1] * n

        def dfs(province, j):
            # j belongs to province
            # now we're looking for node directly connected to i
            # which implies they belonge province

            for k in range(j + 1, n):
                if isConnected[j][k]:
                    # because k connected to i in belong to province
                    # so k can no longer be a province
                    provinces[k] = 0
                    dfs(province, k)

        for i in range(1, n):
            for j in range(i + 1, n):
                if isConnected[i][j]:
                    # j belongs to province i
                    provinces[j] = 0
                    dfs(i, j)

        return sum(provinces)