题目链接：
http://codeforces.com/problemset/problem/650/C
题意：
给定n*m的矩阵，要求用最小的数表示每个元素，其中各行各列的大小关系保持不变。
分析：
将所有元素从小到大排序，然后找到每个元素相应位置进行填充，由于题目要求是每行每列的大小关系保持不变，所以填充的元素应为所在行和所在列中最大元素+1，保存好各行各列当前的最大值，并根据最后填充的元素不断更新就好啦。
问题是如何处理相同元素以及他们所在行列的更新。
这里使用并查集，将相同元素值的位置保存在一个并查集中，这样就可以保证相同元素在新的矩阵中仍然相等~~~使用并查集新姿势get
代码：
#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
#include<stack>
using namespace std;
const int maxn = 1000005;
int pa[maxn], _rank[maxn];
int v[maxn], row[maxn], cal[maxn], nv[maxn];
int m, n;
typedef pair<int, int>pii;
pii p[maxn];
#define fi first
#define se second
void init()
{
for(int i = 0; i < n * m; i++)
pa[i] = i;
}
int _find(int x)
{
if(pa[x]==x) return x;
else return pa[x] = _find(pa[x]);
}
void unite(int x, int y)
{
int rx = _find(x), ry = _find(y);
if(rx == ry) return;
if(_rank[rx]>_rank[ry]) pa[ry]=rx;
else {
pa[rx] = ry;
if(_rank[rx]==_rank[ry]) _rank[ry]++;
}
return;
}
bool same(int x, int y)
{
return _find(x)==_find(y);
}
int main (void)
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n * m; i++){
scanf("%d",&v[i]);
p[i] = pii(v[i], i);
}
init();
for(int i = 0; i < n; i++){
map<int, int>tmp;
for(int j = 0; j < m; j++){
if(tmp.count(v[i * m + j])){
unite(tmp[v[i * m + j]], i * m + j);
}else
tmp[v[i * m + j]] = i * m + j;
}
}
for(int j = 0; j < m; j++){
map<int, int>tmp;
for(int i = 0; i < n; i++){
if(tmp.count(v[i * m + j])){
unite(tmp[v[i * m + j]], i * m + j);
}else
tmp[v[i * m + j]] = i * m + j;
}
}
sort(p, p + n * m);
stack<int>tmp;
for(int i = 0; i < n * m; i++){
int id = p[i].se;
int x = id / m, y = id % m;
nv[_find(id)] = max(nv[_find(id)], max(row[x], cal[y]) + 1);
tmp.push(id);
if(p[i].fi !=p[i + 1].fi){
while(!tmp.empty()){
id =tmp.top(); tmp.pop();
x = id / m, y = id % m;
row[x] = nv[_find(id)];
cal[y] = nv[_find(id)];
}
}
}
for(int i = 0; i < n * m; i++)
printf("%d%c", nv[_find(i)], (i + 1)%m == 0?'
':' ');
return 0;
}
好吧，我真是弱得cry，想了好久。。。