Loading... [来自KeChang](https://blog.silvery.me/) **题目描述：** N个小朋友，编号1∼N，要排成一队。 在安排每个人的顺序时，有M个要求，每个要求包含两个整数a和b，表示小朋友a要排在小朋友b的前面。 请你找出符合所有要求的排队顺序。 **输入格式：** 第一行包含两个整数N和M，表示小朋友的数量和要求的数量。 接下来M行，每行包含两个整数a和b，表示一个排队要求。 **输出格式：** 按排好队列从前到后的顺序在一行内输出每个小朋友的编号。 保证至少存在一个符合条件的顺序。 当符合条件的排队顺序不唯一时，编号更小的小朋友尽量更靠前。 **数据范围：** * 1≤N≤500 * 1≤M≤5000 * 1≤a,b≤N * 保证数对(a,b)各不相同。 **输入样例：** ``` 4 3 1 2 2 3 4 3 ``` **输出样例：** ``` 1 2 4 3 ``` **题目分析：** 拓扑排序，因为需要字典序最小，考虑使用优先队列。 **代码实现：** ``` #include <iostream> #include <queue> #include <bitset> #include <cstring> using namespace std; const int N = 1e3, M = 1e4; int n, m, a, b, idx; int h[N], e[M], ne[M], r[N]; bitset <N> bt; vector <int> ans; priority_queue <int, vector<int>, greater<int>> heap; inline void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++, ++r[b]; } int main () { ios::sync_with_stdio(0); cin.tie(0); memset(h, -1, sizeof h); cin >> n >> m; while (m--) { cin >> a >> b; add(a,b); } for (int i = 1; i <= n; ++i) { if (!r[i]) { bt[i] = 1; heap.push(i); } } while (!heap.empty()) { int i = heap.top(); heap.pop(); ans.push_back(i); for (int t = h[i]; ~t; t = ne[t]) { int& j = e[t]; --r[j]; if (!r[j] && !bt[j]) { bt[j] = 1; heap.push(j); } } } for (auto& i : ans) cout << i << ' '; return 0; } ``` 最后修改：2023 年 08 月 06 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏