c_cmp.cpp

#include <stdc++.h>
#include <iomanip>

using namespace std;

static int curr_point;
static map<int, pair<int, int> > anc_pts;
static vector<int> assoc_tbl;

void rewrite_assoc(int g_old, int g_new) {
    for (int i = 1; i < assoc_tbl.size(); ++i) {
        if (assoc_tbl[i] == g_old) {
            assoc_tbl[i] = g_new;
        }
    }
    assoc_tbl[g_old] = g_new;
}

int create_new_id() {
    ++curr_point;
    assoc_tbl.push_back(curr_point);
    return curr_point;
}

void create_first_anchor(int id, int x, int y) {
    anc_pts[id] = pair<int, int>(x, y);
}

int get_id(int x, int y, const vector<vector<int> >& map) {
    return assoc_tbl[abs(map[x][y])];
}

void fix_new_anchor(int x, int y, int raw_id, vector<vector<int> >& map) {
    int resolved_id = raw_id;
    pair<int, int> old_anc = anc_pts[resolved_id];
    // map[old_anc.first][old_anc.second] = resolved_id;
    anc_pts[resolved_id] = pair<int, int>(x, y);
}

void s_union(int x, int y, vector<vector<int> >& mp, const vector<pair<int, int> >& dsp) {
    int fx, fy;
    int filler = get_id(x, y, mp);

    if (filler == 0) {
        filler = create_new_id();
        create_first_anchor(filler, x, y);

        for (int j = 0; j < dsp.size(); ++j) {
            fx = x + dsp[j].first;
            fy = y + dsp[j].second;

            if ((mp[fx][fy] <= filler) && (mp[fx][fy] >= 0)) // do not overwrite points
                mp[fx][fy] = filler;
        }
        mp[x][y] = -filler;
    } else {
        fix_new_anchor(x, y, filler, mp);
        set<int> ids_list;
        int cid;
        for (int j = 0; j < dsp.size(); ++j) {
            fx = x + dsp[j].first;
            fy = y + dsp[j].second;

            if (mp[fx][fy] < 0) { // Ðÿäîì åñòü âåðøèíà, íóæíî îáúåäèíÿòü îáëàñòè
                ids_list.insert(abs(mp[fx][fy]));
            }

            if ((mp[fx][fy] <= filler) && (mp[fx][fy] >= 0)) {
                mp[fx][fy] = filler;
            }
        }
        /*
        cout << "GET ids_list: \n";
        for (auto sE : ids_list) {
            cout << sE << ' ';
        }
        */

        mp[x][y] = -filler;

        if (ids_list.size() > 0) {
            int area_max = -555;
            vector<int> regions;
            for (set<int>::iterator it = ids_list.begin(); it != ids_list.end(); ++it) {
                if (abs(*it) > area_max) {
                    area_max = abs(*it);
                    regions.push_back(assoc_tbl[abs(*it)]);
                }
            }
            int new_id_ = assoc_tbl[area_max];
            if (area_max > filler) {
                //
                for (int i = 0; i < regions.size(); ++i) {
                    rewrite_assoc(regions[i], new_id_);
                }
            }
            else {
                for (int i = 0; i < regions.size(); ++i) {
                    rewrite_assoc(regions[i], filler);
                }
            }
        }
    }

}

int main(int argc, char** argv) {
    curr_point = 1;
    assoc_tbl = vector<int>(2);
    int n, m, k;
    scanf_s("%d %d %d", &n, &m, &k);

    vector<vector<int> > mapp(n + 2, vector<int>(m + 2, 0));
    vector<pair<int, int> > dsp(8);

    dsp[0] = pair<int, int>(-1, -1);
    dsp[1] = pair<int, int>(0, -1);
    dsp[2] = pair<int, int>(1, -1);
    dsp[3] = pair<int, int>(-1, 0);
    dsp[4] = pair<int, int>(1, 0);
    dsp[5] = pair<int, int>(-1, 1);
    dsp[6] = pair<int, int>(0, 1);
    dsp[7] = pair<int, int>(1, 1);

    int x, y;

    for (int i = 0; i < k; ++i) {
        scanf_s("%d %d", &x, &y);
        s_union(x, y, mapp, dsp);

        /*
        for (int t = 0; t < mapp.size(); ++t) {
            for (int j = 0; j < mapp[t].size(); ++j) {
                cout << setw(3);
                cout << mapp[t][j] << " ";
            }
            cout << "\n";
        }

        for (int t = 1; t < assoc_tbl.size(); ++t) {
            cout << t << " -> " << assoc_tbl[t] << "\n";
        }
        */
    }

    int cansw = 0;
    for (int it = 2; it < assoc_tbl.size(); ++it) {
        if (it == assoc_tbl[it]) {
            ++cansw;
        }
    }

    cout << cansw;

    return 0;
}