C++ DFS solution


  • 0
    M
    class Solution {
    public:
        int findCircleNum(vector<vector<int>>& M) {
            int groups = 0;
            for (int i = 0; i < M.size(); i++) {
                if (visited.find(i) != visited.end()) {
                    continue;
                }
                dfs(M, i);
                groups++;
            }
            
            return groups;
        }
    private:
        unordered_set<int> visited;
        void dfs(vector<vector<int>>& M, int cur) {
            if (visited.find(cur) != visited.end()) {
                return;
            }
            visited.insert(cur);
            for (int i = 0; i < M.size(); i++) {
                if (M[cur][i] == 1) {
                    dfs(M, i);
                }
            }
        }
    };
    

Log in to reply
 

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