19ms short C++ solution with brief explanation (w/out DFS)


  • 0
    V

    For each person, let's count the number of his friends behind him. If he has at least one friend behind him, then he and his friend are in the same friend circle, and this circle will be counted when we consider his friend. Particularly, if he has more than one friend behind him, then we make sure the first person in his "friend group" are now friends with the rest people of the group, so that we do not lose information.
    On the other hand, if the person has no friend behind him, then we know he's the last guy in the friend circle which he belongs to, so we add 1 to the counter.

    class Solution {
    public:
        int findCircleNum(vector<vector<int>>& M) {
            int n = M.size(), count = 0;
            for (int i = 0; i < n; ++i) {
                vector<int> friends;
                for (int j = i + 1; j < n; ++j)
                    if (M[i][j] == 1) friends.push_back(j);
                if (friends.empty())
                    count++;
                else if (friends.size() > 1)
                    for (int j = 1; j < friends.size(); ++j)
                        M[friends[0]][friends[j]] = 1; 
            }
            return count;
        }
    };
    

Log in to reply
 

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