Advertisement
Josif_tepe

Untitled

Mar 22nd, 2024
922
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.78 KB | None | 0 0
  1. //{ Driver Code Starts
  2. // Initial Template for C++
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. // } Driver Code Ends
  8. // User function Template for C++
  9. class Solution {
  10.   public:
  11.     vector<int> idx, sz;
  12.     int root(int x) {
  13.         while(x != idx[x]) {
  14.             idx[x] = idx[idx[x]];
  15.             x = idx[x];
  16.         }
  17.         return x;
  18.     }
  19.     void join(int x, int y) {
  20.         int root_x = root(x);
  21.         int root_y = root(y);
  22.         if(root_x != root_y) {
  23.             if(sz[root_x] > sz[root_y]) {
  24.                 idx[root_y] = idx[root_x];
  25.                 sz[root_x] += sz[root_y];
  26.             }
  27.             else {
  28.                 idx[root_x] = idx[root_y];
  29.                 sz[root_y] += sz[root_x];
  30.             }
  31.         }
  32.     }
  33.     vector<int> numOfIslands(int n, int m, vector<vector<int>> &operators) {
  34.         idx.resize(n * m);
  35.         sz.resize(n * m);
  36.         for(int i = 0; i < n * m; i++) {
  37.             idx[i] = i;
  38.             sz[i] = 1;
  39.         }
  40.         map<pair<int, int>, int> g;
  41.         int cnt = 0;
  42.         for(int i = 0; i < n; i++) {
  43.             for(int j = 0; j < m; j++) {
  44.                 g[make_pair(i, j)] = cnt;
  45.                 cnt++;
  46.             }
  47.         }
  48.         int di[] = {-1, 1, 0, 0};
  49.         int dj[] = {0, 0, -1, 1};
  50.         set<int> st;
  51.         vector<int> res;
  52.         vector<vector<int>> mat(n, vector<int>(m, 0));
  53.         for(int i= 0; i < operators.size(); i++) {
  54.             int ci = operators[i][0], cj = operators[i][1];
  55.             mat[ci][cj] = 1;
  56.             for(int k = 0; k < 4; k++) {
  57.                 int ti = di[k] + ci;
  58.                 int tj = dj[k] + cj;
  59.                
  60.                 if(ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] == 1) {
  61.                     if(st.find(root(g[make_pair(ti, tj)])) != st.end()) {
  62.                         st.erase(st.find(root(g[make_pair(ti, tj)])));
  63.                     }
  64.                     int root_1 = root(g[make_pair(ci, cj)]), root_2 = root(g[make_pair(ti, tj)]);
  65.                     join(root_1, root_2);
  66.                 }
  67.             }
  68.             st.insert(root(g[make_pair(ci, cj)]));
  69.             res.push_back(st.size());
  70.         }
  71.        
  72.         return res;
  73.     }
  74. };
  75.  
  76.  
  77. //{ Driver Code Starts.
  78. int main() {
  79.     int t;
  80.     cin >> t;
  81.     while (t--) {
  82.         int n,m,k; cin>>n>>m>>k;
  83.         vector<vector<int>> a;
  84.        
  85.         for(int i=0; i<k; i++){
  86.             vector<int> temp;
  87.             for(int j=0; j<2; j++){
  88.                 int x; cin>>x;
  89.                 temp.push_back(x);
  90.             }
  91.             a.push_back(temp);
  92.         }
  93.    
  94.         Solution obj;
  95.         vector<int> res = obj.numOfIslands(n,m,a);
  96.        
  97.         for(auto x : res)cout<<x<<" ";
  98.         cout<<"\n";
  99.     }
  100. }
  101.  
  102. // } Driver Code Ends
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement