鏈接：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;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/158165.html
標籤：其他
上一篇：通過python完成 青書學堂刷課 青書視頻 青書教材 課件學習
下一篇：馮·諾依曼計算機特點