链接：https://ac.nowcoder.com/acm/problem/208116 来源：牛客网
题目描述 有N个考生（1<=N<=500），考号依次为1，2，3，。。。。，N进行考试，考试结束后，学校要将所有考生从前往后依次排名，但现在学校不能直接获得每个考生的考试成绩，只知道两人成绩之间的关系，即用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。
输入描述:
输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示考生的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即考生P1的成绩高于P。
输出描述:
给出一个符合要求的排名。输出时考号之间有空格，最后一名后面没有空格。 其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的考生在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。
输入：
3 2 3 1 3 2 17 16 16 1 13 2 7 3 12 4 12 5 17 6 10 7 11 8 11 9 16 10 13 11 15 12 15 13 17 14 17 15 17 16 0 0
输出：
3 1 2 17 6 14 15 12 4 5 13 2 11 8 9 16 1 10 7 3
#include<bits/stdc++.h> #define maxn 505 using namespace std; int n,m,u,v; vector<int> grade[maxn]; //存关系，邻接表 int in[maxn]; //每个结点的入度 set<int> s; //辅助集合，自己排序功能 void topsort(){ if(!s.empty()) s.clear(); //初始化 //入度为0的节点，进入集合 for(int i=1;i<=n;i++) if(!in[i]) s.insert(i); while(!s.empty()){ //取第一个，即（set自动排序）最小的成绩，直接输出，删除 int now = *s.begin(); cout<<now<<" " ; s.erase(now) ; for(int i=0;i<grade[now].size();i++){ //出去一个，与之对应的边也删除，即所对应的结点入度减一 if(--in[grade[now][i]] ==0) { s.insert(grade[now][i]); } } } } int main(){ while(1){ scanf("%d%d",&n,&m); if(n==0&&m==0)break; //多组输入，每次初始化 for(int i=1;i<=n;i++) grade[i].clear(); memset(in,0,sizeof(in)); for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); grade[u].push_back(v); in[v]++; } topsort(); cout<<endl; } }