此题需仔细分析题目，否则题意容易理解错误，应注意下面这种情况
本题意思尽可能让最小的排的靠前，然后次小的尽量靠前，依次下去
如
input：
1
3 1
3 1
output：
3 1 2
解析：我们应让1尽可能的排在前面，然后尽可能的让2排的靠前。。。所以 2 3 1的结果是错误的
思路：拓扑排序（逆向建图+队列）//为解决上述列子，，如果我们正向建图，每次选择入度为零最小的编号输出则无法满足上述案例；
如果我们尝试逆向建图，每次选择入度为零的最大编号输出则刚刚是正确结果的逆序（省赛并查集的逆用，逆向思维的训练）
#include <vector>#include <queue>#include <cstdio>#include <cstring>#include <stack>using namespace std;const int MAX=30010;vector<int> g[MAX];struct node{int x;int y;}wd[100010];struct cmp1{bool operator()(int &a,int &b){return a<b;}};priority_queue<int,vector<int>,cmp1>pq1;int ind[MAX];int n,m;stack<int> st;int main(){int T;scanf("%d",&T);while(T–){scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)g[i].clear();memset(ind,0,sizeof(ind));int x,y;for(int i=1;i<=m;++i){scanf("%d%d",&x,&y);g[y].push_back(x);ind[x]++;}while(!pq1.empty())pq1.pop();for(int i=1;i<=n;++i){if(ind[i]==0)pq1.push(i);}while(!st.empty())st.pop();int tmp;while(!pq1.empty()){tmp=pq1.top();pq1.pop();st.push(tmp);int len=g[tmp].size();for(int i=0;i<len;++i){ind[g[tmp][i]]–;if(ind[g[tmp][i]]==0)pq1.push(g[tmp][i]);}}tmp=st.top();st.pop();while(!st.empty()){printf("%d ",tmp);tmp=st.top();st.pop();}printf("%d\n",tmp);}return 0;}收获：逆向思维的训练（逆向建图，逆向处理等等）
版权声明：本文为博主原创文章，未经博主允许不得转载。
你不能左右天气，但你能转变你的心情
