Share my cute cpp Union Find solution.


  • 0
    M
    int getDaddy(unordered_map<int, int>& dad, int n) {
      if (dad[n] == n) {
        return n;
      }
      
      dad[n] = getDaddy(dad, dad[n]);
      
      return dad[n];
    }
    
    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
      int size = positions.size();
      vector<vector<int>> dir = {{0, 1},{1, 0}, {-1, 0}, {0, -1}};
      unordered_map<int, int> dad;
      vector<int> ans;
      int cnt = 0;
      
      for (auto pos : positions) {
        cnt++;
        dad[pos.first * n + pos.second] = pos.first * n + pos.second;
        
        for (int i = 0; i < 4; i++) {
          int x = pos.first + dir[i][0];
          int y = pos.second + dir[i][1];
          if (x >= 0 && x < m && y >= 0 && y < n) {
            if (dad.count(x * n + y)) {
              int fa = getDaddy(dad, x * n + y);
              int fb = getDaddy(dad, pos.first * n + pos.second);
              
              if (fa == fb) {
                continue;
              }
              
              dad[fa] = fb;
              cnt--;
            }
          }
        }
        ans.push_back(cnt);
      }
      
      return ans;
    }
    

Log in to reply
 

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