Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //{ Driver Code Starts
- // Initial Template for C++
- #include <bits/stdc++.h>
- using namespace std;
- // } Driver Code Ends
- // User function Template for C++
- class Solution {
- public:
- vector<int> idx, sz;
- int root(int x) {
- while(x != idx[x]) {
- idx[x] = idx[idx[x]];
- x = idx[x];
- }
- return x;
- }
- void join(int x, int y) {
- int root_x = root(x);
- int root_y = root(y);
- if(root_x != root_y) {
- if(sz[root_x] > sz[root_y]) {
- idx[root_y] = idx[root_x];
- sz[root_x] += sz[root_y];
- }
- else {
- idx[root_x] = idx[root_y];
- sz[root_y] += sz[root_x];
- }
- }
- }
- vector<int> numOfIslands(int n, int m, vector<vector<int>> &operators) {
- idx.resize(n * m);
- sz.resize(n * m);
- for(int i = 0; i < n * m; i++) {
- idx[i] = i;
- sz[i] = 1;
- }
- map<pair<int, int>, int> g;
- int cnt = 0;
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < m; j++) {
- g[make_pair(i, j)] = cnt;
- cnt++;
- }
- }
- int di[] = {-1, 1, 0, 0};
- int dj[] = {0, 0, -1, 1};
- set<int> st;
- vector<int> res;
- vector<vector<int>> mat(n, vector<int>(m, 0));
- for(int i= 0; i < operators.size(); i++) {
- int ci = operators[i][0], cj = operators[i][1];
- mat[ci][cj] = 1;
- for(int k = 0; k < 4; k++) {
- int ti = di[k] + ci;
- int tj = dj[k] + cj;
- if(ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] == 1) {
- if(st.find(root(g[make_pair(ti, tj)])) != st.end()) {
- st.erase(st.find(root(g[make_pair(ti, tj)])));
- }
- int root_1 = root(g[make_pair(ci, cj)]), root_2 = root(g[make_pair(ti, tj)]);
- join(root_1, root_2);
- }
- }
- st.insert(root(g[make_pair(ci, cj)]));
- res.push_back(st.size());
- }
- return res;
- }
- };
- //{ Driver Code Starts.
- int main() {
- int t;
- cin >> t;
- while (t--) {
- int n,m,k; cin>>n>>m>>k;
- vector<vector<int>> a;
- for(int i=0; i<k; i++){
- vector<int> temp;
- for(int j=0; j<2; j++){
- int x; cin>>x;
- temp.push_back(x);
- }
- a.push_back(temp);
- }
- Solution obj;
- vector<int> res = obj.numOfIslands(n,m,a);
- for(auto x : res)cout<<x<<" ";
- cout<<"\n";
- }
- }
- // } Driver Code Ends
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement