中秋节弱校的一场小比赛的第二题。。SYZOJ
这是第二题，典型的拓扑排序，只是需要添加一个优先队列来保证输出满足字典序。
题比较水，直接贴代码了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <iostream> #include <cstdio> #include <algorithm> #include <queue> using namespace std; const int MX = 1e5 + 5; int n, m, head[MX], tot, cnt, in[MX]; int ans[MX]; bool vis[MX]; struct edge{ int fr, to, ne; }e[1000005]; priority_queue<int, vector<int>, greater<int> > q; void addedge(int a, int b) { tot++; e[tot].fr = a; e[tot].to = b; e[tot].ne = head[a]; head[a] = tot; } void bfs() { for (int i = 1; i <= n; i++) { if (!in[i]) { q.push(i); } } while (!q.empty()) { int now = q.top(); ans[++cnt] = now; q.pop(); for (int i = head[now]; i; i = e[i].ne) { int to = e[i].to; if (vis[to]) continue; in[to]--; if (in[to] != 0) continue; vis[to] = true; q.push(to); } } if (cnt == n) { for (int i = 1; i <= n; i++) { printf("%d ", ans[i]); } printf("\n"); } else { printf("-1\n"); } } int main() { scanf("%d%d", &n, &m); int x, y; for (int i = 1; i <= m; i++) { scanf("%d%d", &x, &y); in[y]++; addedge(x, y); } bfs(); return 0; } |