C++ disjoint set


  • 0
    B
    class Solution {
    public:
        int findCircleNum(vector<vector<int>>& M) {
            //disjoint set
            unordered_map<int,int>friends;
            for(int i = 0; i < M.size(); i++) friends[i] = i;
            for(int i = 0; i < M.size(); i++)
            {
                for(int j = i; j < M.size(); j++)
                {
                    if(M[i][j] == 0) continue;
                    int k = help(friends, i);
                    if(k < friends[j])
                        friends[friends[j]] = k;
                    else
                        friends[k] = friends[j];
                }
            }
            int ans = 0;
            for(int i = 0; i < M.size(); i++)
                if(i == help(friends, i)) ans++;
            return ans;
        }
        
        int help(unordered_map<int,int> & friends, int i)
        {
            if(friends.find(i) == friends.end()) friends[i] = i;
            if(friends[i] != i)
            {
                friends[i] = help(friends, friends[i]);
            }
            return friends[i];
        }
    };

Log in to reply
 

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