Advertisement
Josif_tepe

Untitled

Mar 20th, 2024
567
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.87 KB | None | 0 0
  1. class Solution {
  2.   public:
  3.     vector<int> idx, sz;
  4.     int root(int x) {
  5.         while(idx[x] != x) {
  6.             idx[x] = idx[idx[x]];
  7.             x = idx[x];
  8.         }
  9.         return x;
  10.     }
  11.     void join(int x, int y) {
  12.         int root_x = root(x), root_y = root(y);
  13.         if(root_x != root_y) {
  14.             if(sz[root_x] < sz[root_y]) {
  15.                 idx[root_x] = idx[root_y];
  16.                 sz[root_y] += sz[root_x];
  17.             }
  18.             else {
  19.                 idx[root_y] = idx[root_x];
  20.                 sz[root_x] += sz[root_y];
  21.             }
  22.         }
  23.     }
  24.    
  25.     vector<int> numOfIslands(int n, int m, vector<vector<int>> &operators) {
  26.         // code here
  27.         idx.resize(n * m);
  28.         sz.resize(n * m);
  29.         map<pair<int, int>, int> g;
  30.         int c = 0;
  31.         for(int i = 0; i < n; i++) {
  32.             for(int j = 0; j < m; j++) {
  33.                 g[make_pair(i, j)] = c++;
  34.             }
  35.         }
  36.         for(int i = 0; i < n * m; i++) {
  37.             idx[i] = i;
  38.             sz[i] = 1;
  39.         }
  40.         vector<vector<int>> mat(n, vector<int>(m, 0));
  41.         vector<int> res;
  42.         set<int> st;
  43.         for(int i = 0; i < operators.size(); i++) {
  44.             int ci = operators[i][0], cj = operators[i][1];
  45.             mat[ci][cj] = 1;
  46.             if(ci + 1 < n and mat[ci + 1][cj] == 1) {
  47.                 if(st.find(root(g[make_pair(ci + 1, cj)])) != st.end()) {
  48.                     st.erase(st.find(root(g[make_pair(ci + 1, cj)])));
  49.                 }
  50.                 join(root(g[make_pair(ci, cj)]), root(g[make_pair(ci + 1, cj)]));
  51. //                cout << "DA" << endl;
  52.             }
  53.             if(ci - 1 >= 0 and mat[ci - 1][cj] == 1) {
  54.                 if(st.find(root(g[make_pair(ci - 1, cj)])) != st.end()) {
  55.                     st.erase(st.find(root(g[make_pair(ci - 1, cj)])));
  56.                 }
  57.                 join(root(g[make_pair(ci, cj)]), root(g[make_pair(ci - 1, cj)]));
  58. //                cout << "DA" << endl;
  59.             }
  60.             if(cj + 1 < m and mat[ci][cj + 1] == 1){
  61.                 if(st.find(root(g[make_pair(ci, cj + 1)])) != st.end()) {
  62.                     st.erase(st.find(root(g[make_pair(ci, cj + 1)])));
  63.                 }
  64.                 join(root(g[make_pair(ci, cj)]), root(g[make_pair(ci, cj + 1)]));
  65.             }
  66.             if(cj - 1 >= 0 and mat[ci][cj - 1] == 1) {
  67.                 if(st.find(root(g[make_pair(ci, cj - 1)])) != st.end()) {
  68.                     st.erase(st.find(root(g[make_pair(ci, cj - 1)])));
  69.                 }
  70.                 join(root(g[make_pair(ci, cj)]), root(g[make_pair(ci, cj - 1)]));
  71. //                cout << "DA" << endl;
  72.             }
  73. //            cout << ci << " " << cj << " " << idx[g[make_pair(ci, cj)]] << endl;
  74.             st.insert(root(g[make_pair(ci, cj)]));
  75.             res.push_back((int) st.size());
  76.         }
  77.         return res;
  78.     }
  79. };
  80.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement