LeetCode 547、省份数量

一、题目描述

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

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

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

返回矩阵中省份的数量。

示例 1：

输入：

isConnected = [[1,1,0],[1,1,0],[0,0,1]]

输出：

示例 2：

输入：

isConnected = [[1,0,0],[0,1,0],[0,0,1]]

输出：

二、题目解析

三、参考代码

1、Java 代码

DFS解法

class Solution {
    private void dfs(int[][] isConnected, int[] checkList, int i) {
        // 对于传入的点i，将其标记为已检查过
        checkList[i] = 1;
        // 遍历其他点j
        for (int j = 0; j < isConnected.length; j++) {
            // 1. 若j点未检查过  2. 与i相连  3. j和i不是同一个点
            if (checkList[j] == 0 && isConnected[i][j] == 1 && i != j) {
                // 对j进行DFS
                dfs(isConnected, checkList, j);
            }
        }
    }

    public int findCircleNum(int[][] isConnected) {
        // 获得城市数量
        int n = isConnected.length;
        int ans = 0;
        // 检查列表的长度是n
        int[] checkList = new int[n];

        // 遍历每一个点i
        for (int i = 0; i < n; i++) {
            // 如果该点没检查过，
            if (checkList[i] == 0) {
                // 则从点i出发，进行DFS
                dfs(isConnected, checkList, i);
                // 做完本次DFS，省份数量+1
                ans++;
            }
        }
        return ans;
    }
}

BFS解法

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int ans = 0;
        // 获得城市数量
        int n = isConnected.length;
        // 检查列表的长度是n
        int[] checkList = new int[n];
        // 遍历每一个点i
        for (int i = 0; i < n; i++) {
            if (checkList[i] == 0) { // 若未i检查过
                Queue<Integer> q = new LinkedList<>();
                q.offer(i);           // 把i加入q中，作为BFS的起始位置
                checkList[i] = 1;     // 将i标记为已检查过
                while (!q.isEmpty()) {// 从i开始，进行BFS
                    int x = q.poll();     // 弹出q队头的点x，考虑与其相连的点y
                    for (int y = 0; y < n; y++) { // 遍历其他点y，若y点未检查过，且与x相连
                        if (x != y && checkList[y] == 0 && isConnected[x][y] == 1) {
                            q.offer(y);        // 则把y加入队列中
                            checkList[y] = 1;  // 同时把y标记为已检查过
                        }
                    }
                }
                // 完成本次BFS，省份（连通块）数量+1
                ans++;
            }
        }
        return ans;
    }
}

2、C++ 代码

DFS解法

class Solution {
private:
    void dfs(vector<vector<int>>& isConnected, vector<int>& checkList, int i) {
        // 对于传入的点i，将其标记为已检查过
        checkList[i] = 1;
        // 遍历其他点j
        for (int j = 0; j < isConnected.size(); j++) {
            // 1. 若j点未检查过  2. 与i相连  3. j和i不是同一个点
            if (checkList[j] == 0 && isConnected[i][j] == 1 && i != j) {
                // 对j进行DFS
                dfs(isConnected, checkList, j);
            }
        }
    }

public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        // 获得城市数量
        int n = isConnected.size();
        int ans = 0;
        // 检查列表的长度是n
        vector<int> checkList(n, 0);

        // 遍历每一个点i
        for (int i = 0; i < n; i++) {
            // 如果该点没检查过，
            if (checkList[i] == 0) {
                // 则从点i出发，进行DFS
                dfs(isConnected, checkList, i);
                // 做完本次DFS，省份数量+1
                ans++;
            }
        }
        return ans;
    }
};

BFS解法

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int ans = 0;
        // 获得城市数量
        int n = isConnected.size();
        // 检查列表的长度是n
        vector<int> checkList(n, 0);
        // 遍历每一个点i
        for (int i = 0; i < n; i++) {
            if (checkList[i] == 0) { // 若未i检查过
                queue<int> q;
                q.push(i);            // 把i加入q中，作为BFS的起始位置
                checkList[i] = 1;     // 将i标记为已检查过
                while (!q.empty()) {  // 从i开始，进行BFS
                    int x = q.front();     // 弹出q队头的点x，考虑与其相连的点y
                    q.pop();
                    for (int y = 0; y < n; y++) { // 遍历其他点y，若y点未检查过，且与x相连
                        if (x != y && checkList[y] == 0 && isConnected[x][y] == 1) {
                            q.push(y);        // 则把y加入队列中
                            checkList[y] = 1;  // 同时把y标记为已检查过
                        }
                    }
                }
                // 完成本次BFS，省份（连通块）数量+1
                ans++;
            }
        }
        return ans;
    }
};

3、Python 代码

DFS解法

# 题目：LC547. 省份数量
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：DFS
# 代码看不懂的地方，请直接在群上提问


class Solution:
    def dfs(self, isConnected, checkList, i):
        # 对于传入的点i，将其标记为已检查过  
        checkList[i] = 1
        # 遍历其他点j
        for j in range(self.n):
            # 1. 若j点未检查过  2. 与i相连  3. j和i不是同一个点 
            if checkList[j] == 0 and isConnected[i][j] == 1 and i != j:
                # 对j进行DFS
                self.dfs(isConnected, checkList, j)

    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        # 获得城市数量
        self.n = len(isConnected)
        ans = 0
        # 检查列表的长度是n
        checkList = [0] * self.n

        # 遍历每一个点i
        for i in range(self.n):
            # 如果该点没检查过， 
            if checkList[i] == 0:
                # 则从点i出发，进行DFS    
                self.dfs(isConnected, checkList, i)
                # 做完本次DFS，省份数量+1
                ans += 1            
        return ans

BFS解法

# 题目：LC547. 省份数量
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：BFS
# 代码看不懂的地方，请直接在群上提问


class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        ans = 0
        # 获得城市数量
        n = len(isConnected)
        # 检查列表的长度是n
        checkList = [0] * n
        # 遍历每一个点i
        for i in range(n):
            if checkList[i] == 0:   # 若未i检查过
                q = deque([i])      # 把i加入q中，作为BFS的起始位置
                checkList[i] = 1    # 将i标记为已检查过
                while(q):           # 从i开始，进行BFS
                    x = q.popleft()     # 弹出q队头的点x，考虑与其相连的点y
                    for y in range(n):  # 遍历其他点y，若y点未检查过，且与x相连
                        if x != y and checkList[y] == 0 and isConnected[x][y] == 1:
                            q.append(y)         # 则把y加入队列中
                            checkList[y] = 1    # 同时把y标记为已检查过
                # 完成本次BFS，省份（连通块）数量+1
                ans += 1            
        return ans