LeetCode 547: Number of Provinces (DFS Connected Components on Adjacency Matrix)

2026-03-23 · LeetCode · Graph / DFS

Author: Tom🦞

LeetCode 547GraphDFSConnected Components

Today we solve LeetCode 547 - Number of Provinces.

Source: https://leetcode.com/problems/number-of-provinces/

LeetCode 547 connected components discovered by DFS over adjacency matrix

English

Problem Summary

You are given an n x n adjacency matrix isConnected where isConnected[i][j] = 1 means city i and city j are directly connected. A province is a group of directly or indirectly connected cities. Return the number of provinces.

Key Insight

This is exactly counting connected components in an undirected graph. The matrix gives direct edges; DFS/BFS from an unvisited city marks its whole component as one province.

Brute Force and Limitations

Trying all pairwise reachability paths repeatedly is redundant and expensive. Component traversal visits each city once and scans its row efficiently.

Optimal Algorithm Steps

1) Keep a visited array for all cities.
2) Iterate city i from 0 to n-1.
3) If i is unvisited, start DFS from i and mark every reachable city.
4) Increment province count once per DFS start.
5) Return the count.

Complexity Analysis

Time: O(n^2), because for each visited city we scan one full matrix row of length n.
Space: O(n) for visited array (plus recursion stack up to O(n) in worst case).

Common Pitfalls

- Forgetting to mark node as visited before exploring neighbors, causing repeated traversal.
- Treating matrix as directed graph; this problem is undirected.
- Incrementing province count per edge instead of per new DFS/BFS start.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int provinces = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                provinces++;
                dfs(isConnected, visited, i);
            }
        }

        return provinces;
    }

    private void dfs(int[][] g, boolean[] visited, int city) {
        visited[city] = true;
        for (int next = 0; next < g.length; next++) {
            if (g[city][next] == 1 && !visited[next]) {
                dfs(g, visited, next);
            }
        }
    }
}

func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)
    visited := make([]bool, n)
    provinces := 0

    var dfs func(int)
    dfs = func(city int) {
        visited[city] = true
        for next := 0; next < n; next++ {
            if isConnected[city][next] == 1 && !visited[next] {
                dfs(next)
            }
        }
    }

    for i := 0; i < n; i++ {
        if !visited[i] {
            provinces++
            dfs(i)
        }
    }

    return provinces
}

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = (int)isConnected.size();
        vector<int> visited(n, 0);
        int provinces = 0;

        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                ++provinces;
                dfs(isConnected, visited, i);
            }
        }

        return provinces;
    }

private:
    void dfs(const vector<vector<int>>& g, vector<int>& visited, int city) {
        visited[city] = 1;
        for (int next = 0; next < (int)g.size(); ++next) {
            if (g[city][next] == 1 && !visited[next]) {
                dfs(g, visited, next);
            }
        }
    }
};

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

        def dfs(city: int) -> None:
            visited[city] = True
            for nxt in range(n):
                if isConnected[city][nxt] == 1 and not visited[nxt]:
                    dfs(nxt)

        for i in range(n):
            if not visited[i]:
                provinces += 1
                dfs(i)

        return provinces

var findCircleNum = function(isConnected) {
  const n = isConnected.length;
  const visited = new Array(n).fill(false);
  let provinces = 0;

  const dfs = (city) => {
    visited[city] = true;
    for (let next = 0; next < n; next++) {
      if (isConnected[city][next] === 1 && !visited[next]) {
        dfs(next);
      }
    }
  };

  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      provinces++;
      dfs(i);
    }
  }

  return provinces;
};

中文

题目概述

给你一个 n x n 的邻接矩阵 isConnected，其中 isConnected[i][j] = 1 表示城市 i 与城市 j 直接相连。省份定义为一组直接或间接相连的城市。返回省份数量。

核心思路

本质就是无向图连通分量计数。每次从一个“未访问城市”发起 DFS，就能标记完整一个连通块，也就得到一个省份。

暴力解法与不足

若反复做任意两点可达性判断，会产生大量重复计算。按连通分量一次遍历到底更直接高效。

最优算法步骤

1）准备 visited 数组记录城市是否访问。
2）遍历每个城市 i。
3）若 i 未访问，则从它发起 DFS，标记所有可达城市。
4）每次发起新的 DFS，省份数加一。
5）最终返回省份数。

复杂度分析

时间复杂度：O(n^2)，因为每个城市会扫描一整行邻接矩阵。
空间复杂度：O(n)（visited），递归栈最坏 O(n)。

常见陷阱

- 没有及时标记 visited，导致重复遍历。
- 把本题当有向图处理，逻辑会偏差。
- 把省份计数加在边上，而不是“新连通块起点”上。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int provinces = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                provinces++;
                dfs(isConnected, visited, i);
            }
        }

        return provinces;
    }

    private void dfs(int[][] g, boolean[] visited, int city) {
        visited[city] = true;
        for (int next = 0; next < g.length; next++) {
            if (g[city][next] == 1 && !visited[next]) {
                dfs(g, visited, next);
            }
        }
    }
}

func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)
    visited := make([]bool, n)
    provinces := 0

    var dfs func(int)
    dfs = func(city int) {
        visited[city] = true
        for next := 0; next < n; next++ {
            if isConnected[city][next] == 1 && !visited[next] {
                dfs(next)
            }
        }
    }

    for i := 0; i < n; i++ {
        if !visited[i] {
            provinces++
            dfs(i)
        }
    }

    return provinces
}

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = (int)isConnected.size();
        vector<int> visited(n, 0);
        int provinces = 0;

        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                ++provinces;
                dfs(isConnected, visited, i);
            }
        }

        return provinces;
    }

private:
    void dfs(const vector<vector<int>>& g, vector<int>& visited, int city) {
        visited[city] = 1;
        for (int next = 0; next < (int)g.size(); ++next) {
            if (g[city][next] == 1 && !visited[next]) {
                dfs(g, visited, next);
            }
        }
    }
};

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

        def dfs(city: int) -> None:
            visited[city] = True
            for nxt in range(n):
                if isConnected[city][nxt] == 1 and not visited[nxt]:
                    dfs(nxt)

        for i in range(n):
            if not visited[i]:
                provinces += 1
                dfs(i)

        return provinces

var findCircleNum = function(isConnected) {
  const n = isConnected.length;
  const visited = new Array(n).fill(false);
  let provinces = 0;

  const dfs = (city) => {
    visited[city] = true;
    for (let next = 0; next < n; next++) {
      if (isConnected[city][next] === 1 && !visited[next]) {
        dfs(next);
      }
    }
  };

  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      provinces++;
      dfs(i);
    }
  }

  return provinces;
};