C++ 19ms Union Find


  • 0
    R
    class Solution {
    public:
      int findCircleNum(vector<vector<int>>& M) {
          int n = M.size();
          vector<int> unions(n,0);
          for(int i = 0; i < n; ++i) unions[i] = i;
          
          for(int i = 0; i < n; ++i)
              for(int j = 0; j < n; ++j)
                  if(unions[i] != unions[j] && M[i][j])
                  {
                      int new_group = min(unions[i], unions[j]);
                      int to_update = max(unions[i], unions[j]);
                      for(int k = 0; k < n; ++k)
                      {
                          if(unions[k] == to_update) unions[k] = new_group;
                      }
                  }
          unordered_set<int> groups;
          for(int& u : unions)
              if(groups.count(u)==0) groups.insert(u);
          return groups.size();
      }
      
    };
    

Log in to reply
 

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