本题没有解出实在是不应该，只看难度的话，就是一道非常常规的Medium，可能是太困了，我进入了一种思维误区，把这个表示朋友关系的表当作一个真正的“图”了，来前后左右分别遍历，但其实不是这样，应该只看一个row，这才是某一点的遍历。

    • 设定一个一维数组visited[i]表示第i个人是否已经被访问

    traverse function:

    1. private void traverse(int[][] M, int cur, boolean[] visited) {
    2.     for (int i = 0; i < M.length; ++i) {
    3.         if (!visited[i] && M[cur][i] == 1) {
    4.             visited[i] = true;
    5.             traverse(M, i, visited);
    6.         }
    7.     }
    8. }
    • 时间复杂度: worst case是每个人都需要遍历一下其他人是不是朋友，所以是547. Friend Circles[没有解出] - 图1
    • 空间复杂度: 数组visited，所以是547. Friend Circles[没有解出] - 图2

    代码如下：

    1. class Solution {
    2.   public int findCircleNum(int[][] M) {
    3.     int sz = M.length;
    4.     boolean[] visited = new boolean[sz];
    6.     int cnt = 0;
    7.     for (int i = 0; i < sz; ++i) {
    8.       if (visited[i]) {
    9.         continue;
    10.       }
    11.       visited[i] = true;
    12.       traverse(M, i, visited);
    14.       ++cnt;
    15.     }
    17.     return cnt;
    18.   }
    20.   private void traverse(int[][] M, int cur, boolean[] visited) {
    21.     for (int i = 0; i < M.length; ++i) {
    22.       if (!visited[i] && M[cur][i] == 1) {
    23.         visited[i] = true;
    24.         traverse(M, i, visited);
    25.       }
    26.     }
    27.   }
    28. }