解析

方法一：DFS

遍歷所有人，對(duì)于每一個(gè)人，尋找他的好友，找到好友后再找這個(gè)好友的好友，這樣深度優(yōu)先遍歷下去，設(shè)置一個(gè)visited記錄是否已經(jīng)遍歷了這個(gè)人。 因?yàn)槿绻鹠個(gè)人最多m個(gè)朋友圈，設(shè)置后visited后，相同的朋友圈會(huì)檢測(cè)到visited[i]!=0就會(huì)不算數(shù)

class Solution {
  public int findCircleNum(int[][] M) {
        int res = 0;
        int[] visited = new int[M.length];
        for (int i = 0; i < M.length; i++) {
            if (visited[i] == 0) {
               //沒(méi)有訪問(wèn)到，就把當(dāng)前的組+1，并把可以包含在朋友圈的所有的有關(guān)系的好友標(biāo)記出來(lái)
                res++;
                dfs(M, visited, i);
            }
        }
        return res;
    }
     
    private void dfs(int[][] M, int[] visited, int i) {
        visited[i] = 1;
        for (int j = 0; j < M.length; j++) {
            if (M[i][j] == 1 && visited[j] == 0) {
                dfs(M, visited, j);//在去找這個(gè)好友的好友
            }
             
        }
    }
}

方法二：BFS

import java.util.LinkedList;
import java.util.Queue;
class Solution {
    Queue<Integer> q = new LinkedList<>();
    public void bfs(int[][] M, int[] visited, int i) {
        q.offer(i);
        visited[i] = 1;
        while (!q.isEmpty()) {
            int node = q.poll();
            for (int j = 0; j < M.length; j++) {
                // 未被訪問(wèn)過(guò)且是鄰接點(diǎn),注意是node的鄰接點(diǎn)
                if (visited[j] == 0 && M[node][j] == 1) {
                    // visit[j];
                    q.offer(j);
                    visited[j] = 1;
                }
            }
        }
    }
    public int findCircleNum(int[][] M) {
        int[] visited = new int[M.length];
        int count = 0;
        for (int i = 0; i < M.length; i++) {
            if (visited[i] == 0) {
                bfs(M, visited, i);
                count++;
            }
        }
        return count;
    }
}

方法三：并查集

class Solution {
    private int find(int x, int [] pre){////找到x屬于哪一個(gè)組,如果不是自成一組，在往下找pre[x]屬于哪個(gè)組
        return pre[x]==x ? x :  find(pre[x], pre);
    }
    public int findCircleNum(int[][] M) {
        if (M.length==0)return 0;
        int pre[]=new int[M.length];
        for(int i=0; i<M.length; i++)
            pre[i] = i;//先各自為組，組名也為自己的序號(hào)
        int group = M.length;//一開(kāi)始有多少人就有多少個(gè)朋友圈，當(dāng)每出現(xiàn)一對(duì)朋友時(shí)就減1，最后就是總的朋友圈數(shù)量了。
        for(int i=0; i<M.length; i++){
            for(int j=0; j<M.length; j++){
                if (i != j && M[i][j] == 1){
                    int x1 = find(i, pre);//x1為i所屬的組
                    int x2 = find(j, pre);//x2為j所屬的組
                    if (x1 != x2){
                        //如果不屬于同個(gè)朋友圈的話就把i歸為j的組
                        pre[x1] = x2;
                        group--;
                    }
                }
            }
        }
        return group;
    }
}