AC C++ DFS Solution


  • -1
    class Solution {
    public:
        int findCircleNum(vector<vector<int>>& M) {
            int n = M.size(), circle = 0;
            vector<bool> visited(n, false);
            unordered_map<int, unordered_set<int>> graph;
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < n; c++) {
                    if (M[r][c]) graph[r].insert(c);
                }
            }
            
            for (int i = 0; i < n; i++) {
                if (visited[i]) continue;
                mark(i, graph, visited);
                circle++;
            }
            
            return circle;
        }
        
        void mark(int curr, unordered_map<int, unordered_set<int>>& graph, vector<bool>& visited) {
            visited[curr] = true;
            for (auto next : graph[curr]) {
                if (!visited[next]) mark(next, graph, visited);
            }
        }
    };
    

Log in to reply
 

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