Сжатие таблицы (открытка 2016)

#include <bits/stdc++.h>

using namespace std;

const int sz = 1000005;
int vis[sz], dp[sz];
int p[sz], we[sz];

int get(int a)
{
    if (p[a] == a)
        return a;
    return p[a] = get(p[a]);
}

void unit(int a, int b)
{
    a = get(a);
    b = get(b);
    if (a != b) {
        if (rand() & 1)
            p[a] = b;
        else
            p[b] = a;
    }
}

vector <int> g[sz], rv[sz];
vector <int> path;
vector <vector<int>> a, ans, nxt;
int n, m, t;

void dfs(int u)
{
    vis[u] = 1;
    for (int v : g[u]) {
        if (vis[v] == 0) {
            dfs(v);
        }
    }
    path.push_back(u);
}

void make()
{
    for (int i = 0; i < n; ++i) {
        unordered_map <int, int> lst;
        for (int j = 0; j < m; ++j) {
            int lol = i * m + j;
            if (lst.count(a[i][j])) {
               unit(lol, lst[a[i][j]]);
            }
            lst[a[i][j]] = lol;
        }
    }
    for (int j = 0; j < m; ++j) {
        unordered_map <int, int> lst;
        for (int i = 0; i < n; ++i) {
            int lol = i * m + j;
            if (lst.count(a[i][j])) {
                unit(lol, lst[a[i][j]]);
            }
            lst[a[i][j]] = lol;
        }
    }

    int src = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int k = i * m + j;
            int r = get(k);
            if (we[r] == -1) {
                we[r] = src++;
            }
            nxt[i][j] = we[r];
        }
    }

    t = src;

    for (int i = 0; i < n; ++i) {
        vector <pair<int, int>> sf;
        for (int j = 0; j < m; ++j)
            sf.emplace_back(a[i][j], nxt[i][j]);
        sort(sf.begin(), sf.end());
        int pre = sf[0].second;
        for (int j = 1; j < m; ++j) {
            if (sf[j].second != pre) {
                g[pre].push_back(sf[j].second);
                rv[sf[j].second].push_back(pre);
                pre = sf[j].second;
            }
        }
    }

    for (int j = 0; j < m; ++j) {
        vector <pair<int, int>> sf;
        for (int i = 0; i < n; ++i)
            sf.emplace_back(a[i][j], nxt[i][j]);
        sort(sf.begin(), sf.end());
        int pre = sf[0].second;
        for (int i = 1; i < n; ++i) {
            if (sf[i].second != pre) {
                g[pre].push_back(sf[i].second);
                rv[sf[i].second].push_back(pre);
                pre = sf[i].second;
            }
        }
    }

}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    fill(we, we + sz, -1);

    for (int i = 0; i < sz; ++i)
        p[i] = i;

    cin >> n >> m;
    a.resize(n, vector<int>(m)), ans.resize(n, vector<int>(m)), nxt.assign(n, vector<int>(m, -1));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }

    make();

    for (int i = 0; i < t; ++i) {
        if (!vis[i]) {
            dfs(i);
        }
    }
    reverse(path.begin(), path.end());

    for (int i = 0; i < t; ++i) {
        int cur = path[i];
        dp[cur] = 1;
        for (int j : rv[cur]) {
            dp[cur] = max(dp[cur], dp[j] + 1);
        }
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cout << dp[nxt[i][j]] << " \n"[j == m - 1];

    return 0;
}