此题不是保证字典序，而是要最小的尽量在前面。反向建图，将大的优先级放前面，然后逆序输出。首先反向建图 + + +逆序输出为一个答案。 然后要保证最小的在最前面，因为是逆序输出，所以优先级要反过来。
#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <functional> #include <iostream> #include <map> #include <queue> #include <stack> #include <string> #include <vector> using namespace std; typedef long long ll; const int N = 1e5 + 10, NN = 1e3 + 10, INF = 0x3f3f3f3f; const ll MOD = 1e9 + 7; int num_edge, n, m, sum; int head[N], indegree[N], a[N]; struct Edge { int next; int to; } edge[N]; struct Node { int id; bool friend operator<(const Node& a, const Node& b) { return a.id < b.id; } } node[N]; void add_edge(int from, int to) { num_edge++; edge[num_edge].next = head[from]; edge[num_edge].to = to; head[from] = num_edge; } void topo() { priority_queue<Node> q; for (int i = 1; i <= n; i++) { if (!indegree[i]) { Node newnode; newnode.id = i; q.push(newnode); } } while (!q.empty()) { Node oldnode; oldnode = q.top(); int u = oldnode.id; a[sum++] = u; q.pop(); for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; indegree[v]--; if (!indegree[v]) { Node newnode; newnode.id = v; q.push(newnode); } } } for (int i = sum - 1; i >= 0; i--) { printf("%d", a[i]); printf(i == 0 ? "\n" : " "); } } void init() { num_edge = 0; sum = 0; memset(head, -1, sizeof head); memset(indegree, 0, sizeof indegree); memset(a, 0, sizeof a); } int main() { int t; scanf("%d", &t); while (t--) { init(); scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); add_edge(v, u); indegree[u]++; } topo(); } }