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;
  else
    for (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;
}