# Iterate solution with BFS C++

• This is a matrix & BFS problem, It can also be regarded as a Union find problem. My basic ideal is to find the isolate "island" in the given matrix. The traversing method is different with traditional island problem but still easy to understand.

``````class Solution {
public:
int findCircleNum(vector<vector<int>>& M) {
if(M.size() == 0 || M[0].size() == 0) return 0;
int size = M.size(), ssize = M[0].size();
int res = 0;
vector<bool> touched(size, false);

for(int i = 0; i < size; i++){      //for each person
if(!touched[i]){
res++;
queue<int> myQueue, next;
myQueue.push(i);
touched[i] = true;
while(1){         //find all connected person
while(!myQueue.empty()){
int people = myQueue.front();
myQueue.pop();
for(int j = 0; j < ssize; j++){
if(M[people][j] == 1 && !touched[j]){
touched[j] = true;
next.push(j);
}
}
}
if(next.empty()) break;
myQueue = move(next);
next = queue<int>();
}
}
}
return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.