Problem Description
有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。
Input
输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。
Output
给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。 其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。
Sample Input
4 3 1 2 2 3 4 3
Sample Output
1 2 4 3
Author
SmallBeer(CML)
Source
杭电ACM集训队训练赛（VII）
Recommend
lcy | We have carefully selected several similar problems for you: 1233 2647 3342 1811 1102
Statistic | Submit | Discuss | Note
思路：这个明眼一看拓扑排序模板题啊。可是有个细节就是 排名不唯一时，编号小的优先。这可怎么办呢？
在拓扑排序的过程中，有一点需要注意的是 无论何时在队列中的所有点都是无关联的，即谁排在谁前都行。为什么呢？假设给定的元素是全序关系，即所有点之间都有明确的关系，那么无论何时队列中只有一个点。所以如果在拓扑排序的过程中，如果队列中出现两个及以上的点，则说明这些元素是偏序关系，即有点元素之间可能未明确关系。
所以，把原来的队列换成优先队列就可以了。
AC Code：
#include<iostream> #include<cstring> #include<queue> #include<map> #include<set> #include<stack> #include<cmath> #include<cstdio> #include<iomanip> #include<sstream> #include<algorithm> using namespace std; #define read(x) scanf("%d",&x) #define Read(x,y) scanf("%d%d",&x,&y) #define sRead(x,y,z) scanf("%d%d%d",&x,&y,&z) #define gc(x) scanf(" %c",&x); #define mmt(x,y) memset(x,y,sizeof x) #define write(x) printf("%d\n",x) #define INF 0x3f3f3f3f #define ll long long #define mod 998244353 #define pdd pair<double,double> const int N = 3e6+5; const int M= 2e6+5; int head[1000],tot,cnt; struct Edge { int next; int to; }edge[M]; int deg[1000],a[1000]; inline void add(int from,int to){ edge[++tot].next = head[from]; edge[tot].to = to; head[from] = tot; deg[to]++; } void topsort(int n)//拓扑排序 { priority_queue<int,vector<int> ,greater<int> > Q;//小根堆 for(int i = 1;i <= n;++i) if(deg[i] ==0) Q.push(i); while(Q.size()){ int x = Q.top(); Q.pop(); a[++cnt] = x; for(int i = head[x];~i;i = edge[i].next){ int y = edge[i].to; if(--deg[y]==0) Q.push(y); } } } int main() { int n,m; while(cin>>n>>m){ mmt(head,-1); tot = 0; cnt = 0; int u,v; for(int i = 1;i <= m;++i){ cin>>u>>v; add(u,v); } topsort(n); cout<<a[1]; for(int i = 2;i <= n;++i){ cout<<" "<<a[i]; } puts(""); } }
