547 friend circles

dfs:
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]){
                dfs(i,M,visited);
                count++;            
            }
        }
        return count;
    }
    void dfs(int x,vector<vector<int>>&M,vector<bool>&visited){
        visited[x]=true;
        for(int i=0;i<M[x].size();i++){
            if(M[x][i]==1&&!visited[i]){
                 dfs(i,M,visited);
            }
        }
    }
};
====================================================================================================================================
bfs：

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        vector<bool>visited(M.size(),false);
        int cnt=0;
        queue<int>q;
        for(int i=0;i<M.size();i++){
            if(!visited[i]){
                q.push(i);
                while(q.size()){
                    int x=q.front();
                    q.pop();
                    visited[x]=true;
                    for(int j=0;j<M[x].size();j++){
                        if(M[x][j]==1&&!visited[j]){
                            q.push(j);
                        }
                    }
                }
                cnt++;
            }
        }
        return cnt;
    }
};