#include #include #include #define maxn 100002 using namespace std; int head[maxn], indegree[maxn], ans[maxn]; struct Node{ int to, next; } map[maxn]; void topoSort(int n) { priority_queue, greater > Q; int i, u, id = 1; for(i = 1; i <= n; ++i) if(!indegree[i]) Q.push(i); while(!Q.empty()){ ans[id++] = u = Q.top(); Q.pop(); for(i = head[u]; i != -1; i = map[i].next) if(!--indegree[map[i].to]) Q.push(map[i].to); } for(i = 1; i <= n; ++i) if(i != n) printf("%d ", ans[i]); else printf("%d\n", ans[i]); } int main() { int t, n, m, a, b, i; scanf("%d", &t); while(t--){ memset(indegree, 0, sizeof(indegree)); memset(head, -1, sizeof(head)); scanf("%d%d", &n, &m); for(i = 0; i < m; ++i){ scanf("%d%d", &a, &b); map[i].to = b; map[i].next = head[a]; head[a] = i; ++indegree[b]; } topoSort(n); } return 0; }

AC代码：逆序拓扑

#include 
#include 
#include 
#define maxn 100002
using namespace std;

int head[maxn], indegree[maxn], ans[maxn];
struct Node{
    int to, next;
} map[maxn];

void topoSort(int n)
{
    priority_queue Q;
    int i, u, id = 1;
    for(i = 1; i <= n; ++i)
        if(!indegree[i]) Q.push(i);
    while(!Q.empty()){
        ans[id++] = u = Q.top(); Q.pop();
        for(i = head[u]; i != -1; i = map[i].next)
            if(!--indegree[map[i].to]) Q.push(map[i].to);        
    }    
    for(i = n; i >= 1; --i)
        if(i != 1) printf("%d ", ans[i]);
        else printf("%d\n", ans[i]);
}

int main()
{
    int t, n, m, a, b, i;
    scanf("%d", &t);
    while(t--){
        memset(indegree, 0, sizeof(indegree));
        memset(head, -1, sizeof(head));
        scanf("%d%d", &n, &m);
        for(i = 0; i < m; ++i){
            scanf("%d%d", &a, &b);
            map[i].to = a;
            map[i].next = head[b];
            head[b] = i;
            ++indegree[a];
        }
        topoSort(n);
    }
    return 0;
}

HDU4857 逃生 【拓扑排序】,布布扣,bubuko.com