C++ BFS


  • 0
    G
    class Solution {
    public:
    	int findCircleNum(vector<vector<int>>& M) {
    		int n = M.size(),circleNum = 0;
    		queue<int> iq;
    		set<int> iset;
    		for(int i = 0;i < n;i++) iset.insert(i);
    		for(set<int>::iterator iter = iset.begin();iter != iset.end();){
    			iq.push(*iter);
    			while(!iq.empty()){
    				int num = iq.front();iq.pop();
    				iset.erase(num);
    				for(int i = 0;i < n;i++){
    					if(!M[num][i]) continue; 
    					if(iset.find(i) == iset.end()) continue;
    					iq.push(i);
    				}
    			}
    			circleNum++;
    			iter = iset.begin();
    		}
    		return circleNum;
    	}
    };
    

Log in to reply
 

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