codeforces 274D. Lovely Matrix

题目大意

给你一个n*m的矩阵，其中-1代表可以填入任意非负数
求是否能够通过调换列的顺序，使得每一行变为非递减数列
如果可以，输出调换列的顺序
否则输出-1

思路

可以把每一列看成一个点，那么其实就是把m个点进行排序，使得其满足题目的要求

可以想到使用拓扑排序，拓扑排序的本质是处理有向无环图中的偏序关系，即找到一个线性顺序，使得所有边的约束都被满足，在本题中：每个列是图中的一个节点。每一行的非 -1 元素会生成一系列约束（如列 x 必须在列 y 之前），这些约束作为有向边 x→y 加入图中。
所有行的约束被合并到同一个图中。若图中存在环（如 x→y 和 y→x 同时存在），则无解；否则拓扑排序的结果即为满足所有行约束的列顺序。

对于每一行的x<y的元素，添加一条从x指向y的一条边，但是这样如果有很多重复的数，建边的代价非常大，假设有n个x和m个y,x<y，那么就会建出n*m条边，再加上最外面的n行总复杂度会变成立方级
所以对于相同的数，我们要进行优化，使其变成线性的一条，
这里考虑到使用虚拟节点t,当遇到相同节点x时，通过t指向x节点，x节点指向t+1节点的方式将其变为一条链

使用pair 来存储每个点，first存值，second存位置，然后进行sort刚好能将数组按从小到大的顺序排列，然后在edge数组存位置与位置之间的关系，最后调用拓扑排序得到对应的答案

// Author: zengyz
// 2025-06-13 18:02#include <bits/stdc++.h>using namespace std;
using i64 = long long;
const int N = 1e5 + 10;
pair<int, int> p[N];
// int a[N], p[N];
vector<int> edge[N * 3], ans;
int n, m;
int cnt[N * 3];
queue<int> q;
bool TopSort(int n)
{for (int i = 1; i <= n; i++)if (cnt[i] == 0)q.push(i);for (int i = 1; i <= n; i++){if (q.size() == 0)return 0;int idx = q.front();q.pop();ans.push_back(idx);for (int j = 0; j < edge[idx].size(); j++)if ((--cnt[edge[idx][j]]) == 0)q.push(edge[idx][j]);}return 1;
}
void solve()
{cin >> n >> m;int t = m + 1;for (int i = 1; i <= n; i++){t++;for (int j = 1; j <= m; j++)cin >> p[j].first, p[j].second = j;sort(p + 1, p + 1 + m);int k = 1;while (p[k].first == -1)k++;while (k <= m){int j = k;while (j <= m && p[j].first == p[k].first){edge[t].push_back(p[j].second), cnt[p[j].second]++;edge[p[j++].second].push_back(t + 1), cnt[t + 1]++;}k = j;t++;}}if (TopSort(t) == 0)cout << -1 << endl;elsefor (int i = 0; i < ans.size(); i++){if (ans[i] <= m)cout << ans[i] << " ";}return;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _T = 1;// cin >> _T;while (_T--){solve();}return 0;
}