省份数量

省份数量

DFS

class Solution {
    public int findCircleNum(int[][] isConnected) {
        // 城市数量
        int n = isConnected.length; 
        if (n == 0) return 0;
        // 记录1-n的城市是否被访问过
        boolean[] visited = new boolean[n]; 
        int res = 0;
        
        for (int i = 0; i < n; i++) {
            // 纵向遍历所有城市，发现未访问的城市
            if (!visited[i]) { 
                res++;
                // 遍历该省份所有城市
                dfs(isConnected, visited, i); 
            }
        }
        return res;
    }

    public void dfs(int[][] isConnected, boolean[] visited, int currentCity) {
        // 标记当前城市为已访问，因为是相邻矩阵，所有计算与岛屿有差异，直接标识节点被访问即可
        visited[currentCity] = true; 
        
        // 遍历所有城市，检查与当前城市的连接关系
        for (int neighbor = 0; neighbor < isConnected.length; neighbor++) {
            // 如果两城市相连且邻居城市未被访问
            if (isConnected[currentCity][neighbor] == 1 && !visited[neighbor]) {
                // 递归访问邻居城市
                dfs(isConnected, visited, neighbor); 
            }
        }
    }
}

BFS

class Solution {
    public int findCircleNum(int[][] isConnected) {
        if(isConnected.length == 0){
            return 0;
        }
        int n = isConnected.length;
        boolean[] check = new boolean[n];

        int res = 0;
        for(int i = 0;i < n;i++){
            if(!check[i]){
                res++;
                Deque<Integer> connectedDeque = new ArrayDeque<>();
                connectedDeque.offer(i);
                while(!connectedDeque.isEmpty()){
                    int index = connectedDeque.poll();
                    check[index] = true;

                    for(int j = 0;j < isConnected[0].length;j++){
                        if(isConnected[index][j] == 1&&!check[j]){
                            connectedDeque.offer(j);
                        }
                    }
                }
            }
        }
        return res;
    }
}