Codeforces 274D (168D) Lovely Matrix

問題

nxm行列がlovelyであるとは、行列の各行がそれぞれ単調非減少数列になっていることを言う。
今、lovelyだった行列の要素をいくつか-1に変え、
列をいくつか入れ替えた行列が与えられる。

元の行列としてありうるものをどれか一つ求め、
元の行列のi番目の列には、与えられた行列の何番目の列が対応するかをそれぞれ出力せよ。
存在しない場合は-1を出力せよ。

制約条件

nm≦10^5

方針

i列目にそれぞれに対応する頂点を作り、
a[k][i] < a[k][j]のときにiからjの頂点に辺を張ったグラフを考える。
（ただし、a[k][i]またはa[k][j]が-1のときは張らない）

このグラフがトポロジカルソート可能なら、
そのトポロジカル順が解の一つになっている。

ただし、同じ数字が何度か出てくるので、
a[k][i] < a[k][j]なる頂点全てに辺を張ろうとするとO(nm^2)時間がかかってしまい無理。
そこで、a[k][i]が同じであるようなiから、ダミーの頂点xへ辺を張り、
ダミーの頂点xから、a[k][i] < a[k][j]であるようなjの頂点へ辺を張るようにする。
（ただし、a[k][j]は、a[k][i]より大きいもののうち最小であるもののみでよい）

すると、張る辺の本数は高々O(nm)本になり、
制限時間内にトポロジカルソートが出来るようになる。

ソースコード

int n, m;
vector<vi> e;

int main(){
	cin >> n >> m;
	e.resize((n + 3) * (m + 3));
	int k = m;
	
	rep(i, n){
		vector<pi> p;
		rep(j, m){
			int t;
			cin >> t;
			p.pb(mp(t, j));
		}
		sort(all(p));
		rep(j, m){
			if(p[j].first < 0) continue;
			int nxt = lower_bound(all(p), mp(p[j].first + 1, -1)) - p.begin();
			
			while(j < nxt){
				e[k].pb(p[j].second);
				e[p[j].second].pb(k + 1);
				j++;
			}
			k++;
			j--;
		}
		k++;
	}
	vi ord;
	if(!topologicalSort(e, ord)){
		cout << -1 << endl;
		return 0;
	}
	rep(i, ord.size()) if(ord[i] < m) cout << ord[i] + 1 << " ";
	cout << endl;
	
	return 0;
}