C++ DFS 9 lines 24ms using vectors


  • 0
    V

    Simplified the previously posted solution by using boolean vector instead of hash set.

    void discoverFriends(vector<vector<int>>& m, int row, vector<bool>& circle) {
        circle[row] = true;
        for (auto i = 0; i < m.size(); ++i)
            if (!circle[i] && m[row][i] == 1) discoverFriends(m, i, circle);
    }
    int findCircleNum(vector<vector<int>>& m) {
        vector<vector<bool>> circles;
        for (auto i = 0; i < m.size(); ++i) {
            if (none_of(begin(circles), end(circles), [i](vector<bool>& c){ return c[i];})) {
                circles.push_back(vector<bool>(m.size()));
                discoverFriends(m, i, circles.back());
            }
        }
        return circles.size();
    }
    

Log in to reply
 

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