[LeetCode]: 547. Friend Circles

https://leetcode.com/contest/leetcode-weekly-contest-26/problems/friend-circles/

Solution:
Will use bsf strategy: once find an element with value of 1, put it into a queue; then check all its "neighbors" that are friends with at least one of people in the "element" inside the queue. If the neighbor has a value of 1, indicating they are friends, put it into the queue. After checking all the neighbors, pop out the initial element. Then repeat the above process from the front of the queue until no element left. This is exactly why it is called "Breath Search First". Now we find one circle. We can move on to the rest un-visited elements in the matrix. A visiting matrix is used to label the visiting status of each elements, to make sure each element can only be visited once.

So, the routine procedure for bsf:
1: need a queue;
2: need a visiting matrix for labeling the visiting status.

For this question, we can use the symmetry of the matrix, to make the code a little bit simpler. See code below:

Code:

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int res = 0, n = M.size();
        vector<vector<bool>> v(n, vector<bool>(n, true));
        typedef pair<int, int> tp;
        queue<tp> q;
        for(int i=0; i<n; ++i){
            for(int j=i; j<n; ++j){
                if(M[i][j]==1&&v[i][j]){
                    q.push(tp(i, j));
                    v[i][j]=false;
                    while(q.size()){
                        tp t = q.front();
                        q.pop();
                        int x=t.first, y=t.second;
                        for(int k=0; k<n; ++k){
                            if(v[x][k]&&M[x][k]==1){
                                q.push(tp(x, k));
                                v[x][k]=false;
                            }
                            if(v[k][x]&&M[k][x]==1){
                                q.push(tp(k, x));
                                v[k][x]=false;
                            }
                            if(v[y][k]&&M[y][k]==1){
                                q.push(tp(y, k));
                                v[y][k]=false;
                            }
                            if(v[k][y]&&M[k][y]==1){
                                q.push(tp(k, y));
                                v[k][y]=false;
                            }
                        }
                    }
                    ++res;
                }
            }
        }
        return res;
    }
};