547. Number of Provinces

Leetcode link

题目简介

/**
 * @param {number[][]} isConnected
 * @return {number}
 */

题目给我们一个长度为 n*n 的二维数组，数组元素之可能为 1 或 0（1 表示当前横坐标代表的城市与纵坐标代表的城市连通、0 表示不连通）

规定所有有连通的城市都会被划分为一个省

题目要求我们计算出 isConnected 这个图中有多少个省

解题思路

这道题我们需要用到 DFS 的思想来做

具体而言，我们在遍历图的过程中如果碰到了连通的城市，我们需要深度遍历与其连通的城市，把所有连通的城市串起来

由于 dfs 过程中难免会碰到重复的城市，所以我们可以用一个长度为 n 的 visited 数组来表示到访过的城市

最后我们在最外层遍历数组的时候，如果有碰到未到访过的城市，表示我们遇到了一个新的省，把省的数量加一

最后返回省的数量即可

Javascript

/**
 * @param {number[][]} isConnected
 * @return {number}
 */
var findCircleNum = function (isConnected) {
    const len = isConnected.length
    const visited = Array(len).fill(false)
    let res = 0

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

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

    return res
};

复杂度分析

时间

由于我们需要遍历所有的数组元素，所以是

空间

空间复杂度主要来源于 dfs，最坏的情况下，所有城市都被连在一起，所以是 O(n) 的复杂度