leetcode friend-circles.cpp

class Solution {
public:
  int findCircleNum(vector<vector<int>>& M) {
    int n = M.size();
    int partitions = 0;
    if(!n) return partitions;

    for(int i = 0; i < n; i++){
      if(M[i][i]==1){
        M[i][i] = 0; //instead of using extra mem. to store visited, I alter the matrix.
        partitions++;
        bfs(M, i);
      }
    }

    return partitions;
  }
  
  void bfs(vector<vector<int>>& m, int i){
    queue<int> q;
    q.push(i);
    
    while(!q.empty()){
      int f = q.front();
      q.pop();
      
      for(int j = 0; j < m.size(); j++){ //find f's friends and enqueue them
        if(m[f][j] == 1) {
          q.push(j);
          //switch 1 to 0 to prevent cycles
          m[f][j] = 0;
          m[j][f] = 0;
          m[j][j] = 0;
        }
      }
    }
  }
};