547：朋友圈

问题描述

示例

输入: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
输出: 2 
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。

输入: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，
所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。

思路

这是个连通问题。所以用DFS、BFS、并查集等常见的图算法都可以做。

方法一DFS

class Solution {
    /*
    * 总体思想:
    * 遍历每个人, 对于某人, DFS出他所有的朋友(包括朋友的朋友)
    * */
    public int findCircleNum(int[][] M) {
        if(M == null || M.length == 0) return 0;
        int res = 0;
        boolean[] isVisited = new boolean[M.length];
        for(int i = 0; i < M.length; i++){
            if(!isVisited[i]){// 它自己是它自己的朋友, 所以说只需要判定有没有访问过
                res++;
                findCircleNum(M,isVisited,i);
            }
        }
        return res;
    }
    private void findCircleNum(int[][] M, boolean[] isVisited, int i){
        for(int j = 0; j < M.length; j++){
            if(M[i][j] == 1 && !isVisited[j]){
                isVisited[j] = true;
                findCircleNum(M,isVisited,j);
            }
        }
    }
}

方法二BFS

class Solution {
    public int findCircleNum(int[][] M) {
        if(M == null || M.length == 0) return 0;
        int res = 0;
        boolean[] isvisited = new boolean[M.length];
        for(int i = 0; i < M.length; i++){
            if(!isvisited[i]){
                res++;
                bfs(M,isvisited,i);
            }
        }
        return res;
    }
    private void bfs(int[][] M, boolean[] isvisited, int i){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(i);
        isvisited[i] = true;
        while(!queue.isEmpty()){
            int tmp = queue.poll();
            for(int j = 0; j < M.length; j++){
                if(M[tmp][j] == 1 && !isvisited[j]){ // 避免重复的找
                    queue.add(j);
                    isvisited[j] = true;
                }
            }
        }
    }
}

方法三并查集

class Solution {
    public int findCircleNum(int[][] M) {
        if(M == null || M.length == 0) return 0;
        int res = 0;
        int[] nums = new int[M.length];
        Arrays.fill(nums, -1);
        for(int i = 0; i < M.length; i++){
            for(int j = 0; j < M.length; j++){
                if(M[i][j] == 1 && i != j){
                    union(nums, i, j);
                }
            }
        }
        for(int n: nums) if(n == -1) res++; // 统计
        return res;
    }
    private int find(int[] nums, int i){ // 查
        if(nums[i] == -1) return i;
        return find(nums, nums[i]);
    }
    private void union(int[] nums, int a, int b) { // 并
        int rootA = find(nums, a);
        int rootB = find(nums, b);
        if (rootA != rootB) {
            nums[rootB] = rootA;
        }
    }

}