AcWing RC-u4. RC-u4 拆积木 2023睿抗国赛 (拓扑排序)
原题链接
中等
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 1e6 + 10;
int n, m, idx, id;
int h[M], e[M], ne[M];
int g[2][N];
int din[M], oriIds[M]; // 记录入度 oriIds记录原编号
int ids[M];
struct Node
{
// in 表示入度, id 表示当前点是由上而下,由左至右的第几个(存图所用), oriId 表示原编号
int in, id, oriId;
// in 从小到大 oriId 从小到大
bool operator<(const Node &a) const
{
if (in != a.in)
return in > a.in;
return oriId > a.oriId;
}
};
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof(h));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> g[1][j];
if (ids[g[1][j]] == 0)
{
ids[g[1][j]] = ++id;
}
if (i != 1 && g[1][j] != g[0][j])
{
// 入度 ++
din[ids[g[1][j]]]++;
// 由上一行指向这一行
add(ids[g[0][j]], ids[g[1][j]]);
}
}
for (int j = 1; j <= m; j++)
g[0][j] = g[1][j];
}
priority_queue<Node> heap;
// 枚举所有原编号
for (int i = 1; i < M; i++)
{
// ids[i] 表示 现编号
if (ids[i] != 0)
{
oriIds[ids[i]] = i;
heap.push({din[ids[i]], ids[i], i});
}
}
int cnt = 1;
while (cnt <= id)
{
if (heap.top().in != 0)
{
cout << "Impossible";
break;
}
Node t = heap.top();
heap.pop();
cout << t.oriId;
if (cnt++ != id)
cout << ' ';
for (int i = h[t.id]; ~i; i = ne[i])
{
int j = e[i];
din[j]--;
heap.push({din[j], j, oriIds[j]});
}
}
return 0;
}