C++ DFS 9 lines 24ms using vectors

  • 0

    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];})) {
                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.