Iterate solution with BFS C++


  • 0
    B

    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;
        }
    };
    

Log in to reply
 

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