C++ BFS solution


  • 0
    S

    I would call this kind of problem as perfect BFS problem. Because one condition to use BFS is to find all connected components in a graph. A similar question is LC323. My solution for LC323: https://discuss.leetcode.com/topic/101087/clean-c-bfs-solution. You could find they are the same structure.

    
    class Solution {
    public:
        int findCircleNum(vector<vector<int>>& M) {
            int ret = 0;
            vector<bool> visited(M.size(), false);
            for ( int i = 0; i < visited.size(); i++ ) {
                if(!visited[i]) 
                {
                    bfs(i, visited, M);
                    ret++;
                }
            }
            return ret;
        }
    private:
        void bfs(int i, vector<bool>& visited, vector<vector<int>>& M) {
            visited[i] = true;
            queue<int> Q;
            Q.push(i);
            while (!Q.empty()) {
                int cur = Q.front();
                Q.pop();
                for ( int j = 0; j < M[cur].size(); j++ ) {
                    if ( M[cur][j] == 1 && !visited[j] ) {
                        visited[j] = true;
                        Q.push(j);
                    }
                }
            }
    
        }
    };
    

Log in to reply
 

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