算法
(拓扑排序) $O(N\log N)$
本题是经典的由 $A_i$ 指向 $B_i$ 所制成的有向图的拓扑排序问题,而最小字典序只需用小根堆来维护即可。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::greater;
using std::priority_queue;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> to(n);
vector<int> deg(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
deg[b]++;
}
priority_queue<int, vector<int>, greater<int>> q;
rep(i, n) if (deg[i] == 0) q.push(i);
vector<int> ans;
while (q.size()) {
int v = q.top(); q.pop();
ans.push_back(v);
for (int u : to[v]) {
deg[u]--;
if (deg[u] == 0) q.push(u);
}
}
if (ans.size() != n) puts("-1");
else {
for (int v : ans) cout << v+1 << '\n';
}
return 0;
}