🌆 省份数量

📝 题目描述

​ 有n个城市，其中一些彼此相连，另一些没有相连。如果城市a与城市b直接相连，且城市b与城市c直接相连，那么城市a与城市c间接相连。

​ 省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。

​ 给你一个n x n的矩阵isConnected，其中isConnected[i][j] == 1表示第i个城市和第j个城市直接相连，而isConnected[i][j] == 0表示二者不直接相连。

​ 返回矩阵中省份的数量。

📋 代码模板

java

class Solution {
    public int findCircleNum(int[][] isConnected) {

    }
}

typescript

function findCircleNum(isConnected: number[][]): number {
    
}

💡 提示

1. $1<=n<=200$
2. $n==isConnected.length$
3. $n==isConnected[i].length$
4. $isConnected[i][j]$ 为1或0
5. $isConnected[i][i]==1$
6. $isConnected[i][j]==isConnected[j][i]$

🚀 示例

🖊️ 题解

DFS

可惜没有如果

java

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]) {
                dfs(isConnected, visited, i);
                provinces++;
            }
        }
        return provinces;
    }

    private void dfs(int[][] isConnected, boolean[] visited, int i) {
        if (visited[i]){
            return;
        }
        visited[i] = true;
        for (int j = 0; j < isConnected.length; j++) {
            if (isConnected[i][j] == 1) {
                dfs(isConnected, visited, j);
            }
        }
    }
}

typescript

function findCircleNum(isConnected: number[][]): number {
    const n = isConnected.length;
    const visited: boolean[] = Array(n).fill(false);
    let provinces = 0;
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(isConnected, visited, i);
            provinces++;
        }
    }
    return provinces;
}

function dfs(isConnected: number[][], visited: boolean[], i: number): void {
    if (visited[i]) {
        return;
    }
    visited[i] = true;
    for (let j = 0; j < isConnected.length; j++) {
        if (isConnected[i][j] == 1) {
            dfs(isConnected, visited, j);
        }
    }
}

BFS

可惜没有如果

java

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        int provinces = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                queue.offer(i);
                visited[i] = true;
                while (!queue.isEmpty()) {
                    int j = queue.poll();
                    for (int k = 0; k < n; k++) {
                        if (isConnected[j][k] == 1 && !visited[k]) {
                            queue.offer(k);
                            visited[k] = true;
                        }
                    }
                }
                provinces++;
            }
        }
        return provinces;
    }
}

typescript

function findCircleNum(isConnected: number[][]): number {
    const n = isConnected.length;
    const visited: boolean[] = Array(n).fill(false);
    const queue: number[] = [];
    let provinces = 0;
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            queue.push(i);
            visited[i] = true;
            while (queue.length > 0) {
                const j: number = queue.shift()!;
                for (let k = 0; k < n; k++) {
                    if (isConnected[j][k] == 1 && !visited[k]) {
                        queue.push(k);
                        visited[k] = true;
                    }
                }
            }
            provinces++;
        }
    }
    return provinces;
}

💭 复杂度分析