题目链接
https://www.acwing.com/problem/content/850/
解析
要掌握拓扑排序的基本思路:每次找到入度为0的点加入队列,可以用数组存答案,根据加入队列的数的个数可以判断是否可以进行拓扑排序。
Ac代码
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int N = 1e5 + 10; int h[N], e[N], ne[N], idx; int n, m; int du[N], ans[N], x; void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++; } bool topsort() { queue<int> q; for(int i = 1; i <= n; i ++) if(du[i] == 0) q.push(i); while(q.size()){ auto t = q.front(); q.pop(); ans[x ++] = t; for(int i = h[t]; i != -1; i = ne[i]){ int j = e[i]; du[j] --; if(!du[j]){ q.push(j); } } } if(x < n) return false; return true; } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while(m --){ int a, b; scanf("%d%d", &a, &b); add(a, b); du[b] ++; } if(!topsort()){ printf("-1\n"); } else{ for(int i = 0; i < x; i ++) printf("%d ", ans[i]); puts(""); } return 0; }