Number of Islands (DSU Approach)

#include <bits/stdc++.h>
using namespace std;

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

class DS{
    public:
    map<pair<int, int>, pair<int, int> > parent;
    map<pair<int, int>, int > size;

    DS(){}

    DS(int n, int m){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                parent[{i, j}] = {i, j};
                size[{i, j}] = 1;
            }
        }
    }


    pair<int, int> find(int r, int c){
        if(make_pair(r, c) == parent[{r, c}]){
            return {r, c};
        }
        auto p = parent[{r, c}];
        return parent[{r, c}] = find(p.first, p.second);
    }

    void Union(int u1, int v1, int u2, int v2){
        pair<int, int> a = find(u1, v1), b = find(u2, v2);

        int ar = a.first, ac = a.second, br = b.first, bc = b.second;

        if(a != b){
            if(size[{ar, ac}] >= size[{br, bc}]){
                parent[{br, bc}] = {ar, ac};
                size[{ar, ac}] += size[{br, bc}];
            }
            else{
                parent[{ar, ac}] = {br, bc};
                size[{br, bc}] += size[{ar, ac}];
            }
        }
    }
};

bool isValid(int nr, int nc, int n, int m){
    if(nr < 0 || nr >= n || nc < 0 || nc >= m){
        return false;
    }
    return true;
}

vector<int> numOfIslands(int n, int m, vector<vector<int> > &operations){
    vector<int> res;
    vector<vector<int> > matrix(n, vector<int>(m, 0));
    DS dsu(n, m);
    int islands = 0;
    for(int i = 0; i < operations.size(); i++){
        int r = operations[i][0], c = operations[i][1];

        //If queries are repeated, such as [(1, 2), (1, 2)]
        //If not continued, it will again do islands++, but it was already done.
        if(matrix[r][c] == 1){
            res.push_back(islands);
            continue;
        }
        matrix[r][c] = 1;
        islands++;
        set<pair<int, int> > cc;
        for(int k = 0; k < 4; k++){
            int nr = r + dx[k], nc = c + dy[k];
            if(isValid(nr, nc, n, m)){
                if(matrix[nr][nc] == 1 && cc.count(dsu.find(nr, nr)) == 0){
                    islands--;
                    dsu.Union(r, c, nr, nc);
                    cc.insert(dsu.find(nr, nc));
                    //don't break, it is possible that any of the neighbour can have 1
                    //it will combine every neighbour into 1 cc
                    //break;
                }
            }
        }
        res.push_back(islands);
    }
    return res;
}

int main() {
    // your code goes here
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int> > operations(k, vector<int>(2));
    for(int i = 0; i < k; i++){
        cin >> operations[i][0] >> operations[i][1];
    }
    vector<int> res =  numOfIslands(n, m, operations);
    for(int i = 0; i < res.size(); i++){
        cout << res[i] << " ";
    }
}