20-line C++ DFS Solution


  • 1

    The main idea is a friend circle is a connected graph

    class Solution {
    public:
        unordered_map<int, unordered_set<int>> friends; // the friendship graph
        unordered_set<int> visited;
        int findCircleNum(vector<vector<int>>& M) {
            int ans=0;
            for(int i=0;i<M.size();i++) // build the graph
                for(int j=0;j<M.size();j++)
                    if(i!=j&&M[i][j])
                        friends[i].insert(j); 
            for(int i=0;i<M.size();i++) // explore the graph to see how many isolated graphs
                if(visited.count(i)==0) {
                    ans++;
                    exploreFriends(i);
                }
            return ans;
        }
        
        void exploreFriends(int i) { // DFS
            visited.insert(i);
            for(auto it : friends[i]) 
                if(visited.count(it)==0)
                    exploreFriends(it);
        }
    };
    

Log in to reply
 

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