Graph Connected Components的题目。枚举所有的人,每个人找所有朋友,找到的朋友全部mark掉,剩下的人再开始找朋友。
Time complexity: O(n^2) Space complexity: O(n)
class Solution {
public int findCircleNum(int[][] M) {
int count = 0;
boolean[] visited = new boolean[M.length];
for (int i = 0; i < M.length; i++) {
if (!visited[i]) {
count ++;
findCircleNumHelper(i, visited, M);
}
}
return count;
}
private void findCircleNumHelper(int i, boolean[] visited, int[][] M) {
if (visited[i]) {
return;
}
visited[i] = true;
for (int j = 0; j < M.length; j++) {
if (i == j) {
continue;
}
if (M[i][j] == 1) {
findCircleNumHelper(j, visited, M);
}
}
}
}