題目
班上有 N 名學(xué)生揪阶。其中有些人是朋友，有些則不是患朱。他們的友誼具有是傳遞性鲁僚。如果已知 A 是 B 的朋友，B 是 C 的朋友裁厅，那么我們可以認(rèn)為 A 也是 C 的朋友冰沙。所謂的朋友圈，是指所有朋友的集合姐直。
給定一個(gè) N * N 的矩陣 M倦淀，表示班級(jí)中學(xué)生之間的朋友關(guān)系蒋畜。如果M[i][j] = 1声畏，表示已知第 i 個(gè)和 j 個(gè)學(xué)生互為朋友關(guān)系，否則為不知道姻成。你必須輸出所有學(xué)生中的已知的朋友圈總數(shù)插龄。
示例 1:
輸入:
[[1,1,0],
[1,1,0],
[0,0,1]]
輸出: 2
說(shuō)明：已知學(xué)生0和學(xué)生1互為朋友，他們?cè)谝粋€(gè)朋友圈科展。
第2個(gè)學(xué)生自己在一個(gè)朋友圈均牢。所以返回2。
示例 2:
輸入:
[[1,1,0],
[1,1,1],
[0,1,1]]
輸出: 1
說(shuō)明：已知學(xué)生0和學(xué)生1互為朋友才睹，學(xué)生1和學(xué)生2互為朋友徘跪，所以學(xué)生0和學(xué)生2也是朋友甘邀，所以他們?nèi)齻€(gè)在一個(gè)朋友圈，返回1垮庐。
解題思路
使用dfs松邪，深度優(yōu)先，訪問(wèn)M數(shù)組哨查，對(duì)于已經(jīng)訪問(wèn)過(guò)的逗抑，變?yōu)閠rue，下次就不再訪問(wèn)寒亥。
代碼
class Solution {
public:
int findCircleNum(vector<vector<int > >& M)
{
vector<bool> visited(M.size(), false);
int count = 0;
for(int i= 0; i < M.size(); i ++){
if(!visited[i]){
visit(M, i, visited);
count++;
}
}
return count;
}
void visit(vector<vector<int > >& M, int i, vector<bool >& visited)
{
visited[i] = true;
for (int j = 0; j < M.size(); j++) {
if (j != i && M[i][j] == 1 && !visited[j]) visit(M, j, visited);
}
}
};
