P36-省份数量-广度递归

//省份数量
/*
* 有n个城市，其中一些彼此相连，另一些没有相连。如果城市a与城市b直接相连，且城市b与城市c直接相连，
* 那么城市a与城市c间接相连
* 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
* 给你一个 n * n 的矩阵 isConnected，其中isConnected[i][j]=1表示第i个城市和第j个城市直接相连，
* 而isConnected[i][j]=0表示二者不直接相连
* 返回矩阵中省份（直接或间接相连的是一个省，没有关联的是另一个省）的数量
* */
public class P36 {
    public static void main(String[] args) {
        System.out.println(getProvince(new int[][]{{1,1,0},{1,1,0},{0,0,1}}));  //2
        System.out.println(getProvince(new int[][]{{1,0,0},{0,1,0},{0,0,1}}));  //3
    }

    //广度优先，基本上遇到广度就是queue，先进先出
    private static int getProvince(int[][] citiesConnected) {

        int cities = citiesConnected.length;        //城市数
        boolean[] visited = new boolean[cities];    //标记是否已经访问过

        int provinces = 0;
        Queue<Integer> queue = new LinkedList<>();

        for(int i=0; i<cities; i++){
            if(!visited[i]){        //城市未被访问
                queue.offer(i);     //入队
                while(!queue.isEmpty()){    //一圈圈的找
                    int k = queue.poll();   //出队
                    visited[k] = true;      //标记已访问
                    for(int j=0; j<cities; j++){
                        if(citiesConnected[i][j] == 1 && !visited[j]){
                            queue.offer(j);     //和i相连的入队
                        }
                    }
                }
                provinces++;
            }
        }

        return provinces;
    }

}