問題描述
在一個班級里有N個同學， 有些同學是朋友畴蒲，有些不是。他們之間的友誼是可以傳遞的比如A和B是朋友，B和C是朋友补胚，那么A和C也是朋友握联。我們定義 friend circle為由直接或者間接都是朋友組成的group.
給定N*N 數(shù)組 M 代表同學之間的關系. 如果M[i][j] = 1, 那么i 和 j 同學是朋友代芜，現(xiàn)在我們需要輸出friend circles 的數(shù)量
Example 1:
Input:
[[1,1,0],
[1,1,0],
[0,0,1]]
Output: 2
解釋: 0和1號同學是朋友，所以他們是一個friend cricle，2號同學自己是個friend circle窟哺，所有返回2阿蝶。
Example 2:
Input:
[[1,1,0],
[1,1,1],
[0,1,1]]
Output: 1
解釋: 0號同學和1號同學是朋友筑煮，1號和2號同學是朋友虑凛，那么0,1,2都是朋友锣披，他們組成一個friend circle盅粪，所以結果返回1
Note
N is in range [1,200].
M[i][i] = 1 for all students.
If M[i][j] = 1, then M[j][i] = 1.
分析
我們可以將給定的M數(shù)組看做是一個graph, M[i][j] = 1 表示節(jié)點i 和 j 相連番刊，那么尋找fridend circle的問題熔吗，轉(zhuǎn)化為圖遍歷的問題咨堤，求fiend circle的個數(shù)實則為求連通圖的個數(shù)。解決這類問題通常使用DFS或者BFS去更新一個visited數(shù)組狐赡，對每個未訪問的節(jié)點調(diào)用圖形遍歷算法，每次調(diào)用苔咪，所有相連節(jié)點的狀態(tài)都會被更新，那么friend cicle的數(shù)量則為調(diào)用遍歷的次數(shù)。
DFS實現(xiàn)
public int findCircleNum(int[][] M) {
int N = M.length;
boolean[] visited = new boolean[N];
int cnt = 0;
for(int i = 0; i < N; i++){
if(!visited[i]){
dfs(M, visited, i);
cnt++;
}
}
return cnt;
}
private void dfs(int[][] M, boolean[] visited, int i){
visited[i] = true;
for(int j = 0; j < M.length; j++){
if(M[i][j] == 1 && !visited[j]){
dfs(M, visited, j);
}
}
}
時間復雜度：O(n^2)，總體上要遍歷M數(shù)組的所有位置
空間復雜度：O(n)
BFS實現(xiàn)
public int findCircleNum(int[][] M) {
boolean[] visited = new boolean[M.length];
int count = 0;
Queue < Integer > queue = new LinkedList < > ();
for (int i = 0; i < M.length; i++) {
if (!visited[i]) {
queue.add(i);
while (!queue.isEmpty()) {
int s = queue.remove();
visited[s] = true;
for (int j = 0; j < M.length; j++) {
if (M[s][j] == 1 && !visited[j]])
queue.add(j);
}
}
count++;
}
}
return count;
}
時間復雜度：O(n^2)，總體上要遍歷M數(shù)組的所有位置
空間復雜度：O(n)
