FORCE-T1012B: Chemical Table

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

typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

const int N = 2e5;

bool foundRow[N + 1], foundCol[N + 1];
int ds[N + 1], sz[N + 1];
vector<pii> colrowPairs;
vector<tiii> edges;

int dsFind(int u){
    if(ds[u] == u){
        return u;
    }
    return ds[u] = dsFind(ds[u]);
}

int main(){

    int row, col, nChem;
    scanf("%d%d%d", &row, &col, &nChem);
    if(nChem == 0){
        cout << row + col - 1;
        return 0;
    }
    for(int i = 1; i <= row; ++i){
        ds[i] = i;
        sz[i] = 1;
    }
    int r, c;
    for(int i = 1; i <= nChem; ++i){
        scanf("%d%d", &r, &c);
        foundCol[c] = true;
        foundRow[r] = true;
        colrowPairs.emplace_back(c, r);
    }
    int sum = 0;
    for(int i = 1; i <= row; ++i){
        if(!foundRow[i]){
            ++sum;
            colrowPairs.emplace_back(c, i);
        }
    }
    for(int i = 1; i <= col; ++i){
        if(!foundCol[i]){
            ++sum;
            colrowPairs.emplace_back(i, r);
        }
    }

    sort(colrowPairs.begin(), colrowPairs.end());
    for(int i = 0; i < (int)colrowPairs.size() - 1; ++i){
        int w = colrowPairs[i + 1].first - colrowPairs[i].first;
        int u = colrowPairs[i].second;
        int v = colrowPairs[i + 1].second;
        edges.emplace_back(w, u, v);
    }
    sort(edges.begin(), edges.end());

    for(tiii t : edges){
        int w = get<0>(t);
        int u = get<1>(t);
        int v = get<2>(t);
        u = dsFind(u);
        v = dsFind(v);
        if(u != v){
            if(sz[u] < sz[v]){
                swap(u, v);
            }
            ds[v] = u;
            sz[u] += sz[v];
            sum += w;
        }
    }
    cout << sum;

    return 0;
}

// AQUABLITZ'S SOLUTION
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5;
const int M = 2e5;

int ds[N + M + 1], sz[N + M + 1];

int dsFind(int u){
    if(ds[u] == u){
        return u;
    }
    return ds[u] = dsFind(ds[u]);
}

int main(){

    int row, col, nChem;
    scanf("%d%d%d", &row, &col, &nChem);
    for(int i = 1; i <= row + col; ++i){
        ds[i] = i;
        sz[i] = 1;
    }
    int compCnt = row + col;
    for(int i = 1; i <= nChem; ++i){
        int u, v;
        scanf("%d%d", &u, &v);
        v += row;
        u = dsFind(u);
        v = dsFind(v);
        if(u != v){
            if(sz[u] < sz[v]){
                swap(u, v);
            }
            ds[v] = u;
            sz[u] += sz[v];
            --compCnt;
        }
    }
    cout << compCnt - 1;

    return 0;
}