题目链接：

---

 

一种比较容易想到的做法是把进行拓扑排序的队列换成优先队列，每次取出能访问到的编号最小的点，但这样是不对的，很容易构造数据卡掉。

正确的做法是建反向图，每次取出编号最大的，再将生成的拓扑序逆序输出即可。

第一种做法并不能保证小的编号尽量靠前，因为每次取的当前能访问到的最小的；第二种方法，相当于尽量先把编号较大的取走，实在不能取了才去取编号小的，因此逆序以后就是要求的序列。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6  7 using namespace std; 8  9 inline int get_num() {10     int num = 0;11     char c = getchar();12     while (c < '0' || c > '9') c = getchar();13     while (c >= '0' && c <= '9')14         num = num * 10 + c - '0', c = getchar();15     return num;16 }17 18 const int mmax = 1e5 + 5;19 20 int head[mmax], eid;21 22 struct Edge {23     int v, next;24 } edge[mmax];25 26 inline void insert(int u, int v) {27     edge[++eid].v = v;28     edge[eid].next = head[u];29     head[u] = eid;30 }31 32 int ind[mmax];33 34 priority_queue
           
             q;35 stack
            
              ans;36 37 int main() {38 int d = get_num();39 while (d--) {40 int n = get_num(), m =get_num();41 memset(head, 0, sizeof(head));42 memset(ind, 0, sizeof(ind));43 eid = 0;44 for (int i = 1; i <= m; ++i) {45 int u = get_num(), v = get_num();46 insert(v, u);47 ++ind[u];48 }49 for (int i = 1; i <= n; ++i)50 if (!ind[i]) q.push(i);51 while (!q.empty()) {52 int u = q.top();53 q.pop();54 ans.push(u);55 for (int p = head[u]; p; p = edge[p].next) {56 int v = edge[p].v;57 if (!(--ind[v])) q.push(v);58 }59 }60 if ((int)ans.size() != n) {61 printf("Impossible!\n");62 while (!ans.empty()) ans.pop();63 } else {64 while (!ans.empty()) {65 printf("%d ", ans.top());66 ans.pop();67 }68 printf("\n");69 }70 }71 return 0;72 }