CF 651.E-Table Compression---进阶并查集

Little Petya is now fond of data compression algorithms. He has already studied gz, bz, zip algorithms and many others. Inspired by the new knowledge, Petya is now developing the new compression algorithm which he wants to name dis.

Petya decided to compress tables. He is given a table a consisting of n rows and m columns that is filled with positive integers. He wants to build the table a’ consisting of positive integers such that the relative order of the elements in each row and each column remains the same. That is, if in some row i of the initial table ai, j < ai, k, then in the resulting table a’i, j < a’i, k, and if ai, j = ai, k then a’i, j = a’i, k. Similarly, if in some column j of the initial table ai, j < ap, j then in compressed table a’i, j < a’p, j and if ai, j = ap, j then a’i, j = a’p, j.

Because large values require more space to store them, the maximum value in a’ should be as small as possible.

Petya is good in theory, however, he needs your help to implement the algorithm.

Input
The first line of the input contains two integers n and m (, the number of rows and the number of columns of the table respectively.

Each of the following n rows contain m integers ai, j (1 ≤ ai, j ≤ 109) that are the values in the table.

Output
Output the compressed table in form of n lines each containing m integers.

If there exist several answers such that the maximum number in the compressed table is minimum possible, you are allowed to output any of them.

cf题目

题意：
给定一组矩阵，要求缩小矩阵中的数，满足条件：
1.对于每行与每列，行和列内仍然为原相对大小
2.对于每行每列，行列内原来相等的数之后也要相等

题解：
拓扑排序，先进行整体跨行列sort排序，保证操作从绝对最小数开始，并且用并查集将有相等关系（在对原数组排序时基本可以确定）的位置连接起来一起排序，最后从根节点（绝对最小结点）进行升序操作

#include<iostream>
#include<memory.h>
#include<algorithm>
#include<cstdio>
using namespace std;
int i, j, k, n, m, T, tot;
const int N = 1000100;
struct dat {//存储row，column,value和拓扑排序的位次
    int r, c, v, id;
}p[N];
bool cmp(const dat & a, const dat & b) { return a.v < b.v; }
int f[N], X[N], Y[N], ans[N], x[N], y[N], tmp[N];
int Find(int a) { return a == f[a] ? f[a] : f[a] = Find(f[a]); }//并查集
int main(){
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++) {
            scanf("%d", &p[++tot].v);
            p[tot].r = i, p[tot].c = j;
            p[tot].id = tot;//序列初始位次tot
            f[tot] = tot;//初始化父节点
        }
    sort(p + 1, p + 1 + tot, cmp);//按照原值进行第一次排序，保证严格升序（即从相对值最小的结点开始操作）
    for (i = 1; i <= tot; i = j) {
        for (j = i; p[i].v == p[j].v; ++j);//寻找相同的值
        for (k = i; k < j; k++) {//对所有相同的值进行列+行的连接操作，使其保持一致
            int r = p[k].r, c = p[k].c;
            if (!x[r]) x[r] = k;
            else f[Find(k)] = Find(x[r]);
            if (!y[c]) y[c] = k;
            else f[Find(k)] = Find(y[c]);
        }
        for (k = i; k < j; k++) {//将所有彼此相连的结点，根据已有值赋值
            int q = Find(k);
            tmp[q] = max(tmp[q], max(X[p[k].r], Y[p[k].c]) + 1);
        }
        for (k = i; k < j; k++) {//由根节点（最小结点）进行递增操作
            x[p[k].r] = y[p[k].c] = 0;//对行列原值进行清空
            X[p[k].r] = Y[p[k].c] = ans[p[k].id] = tmp[Find(k)];//永久赋值
        }
    }
    for (i = 1; i <= tot; i++) {
        printf("%d ", ans[i]);
        if (i % m == 0) puts("");
    }
}