排名

時(shí)間限制: 1 Sec 內(nèi)存限制: 128 MB

題目描述

有 N 個(gè)比賽隊(duì)（1<=N<=500），編號(hào)依次為 1，2，3……N 進(jìn)行比賽，比賽結(jié)束后，裁判委員會(huì)要將所有參賽隊(duì)伍從前往后依次排名，但現(xiàn)在裁判委員會(huì)不能直接獲得每個(gè)隊(duì)的比賽成績，只知道每場(chǎng)比賽的結(jié)果，即 P1 贏 P2，用 P1，P2 表示，排名時(shí) P1 在 P2之前?，F(xiàn)在請(qǐng)你編程序確定排名。

符合條件的排名可能不是唯一的。此時(shí)要求輸出時(shí)編號(hào)小的隊(duì)伍在前。輸入數(shù)據(jù)保證是正確的，即輸入數(shù)據(jù)確保一定能有一個(gè)符合要求的排名。

輸入

輸入有若干組。每組中的第一行為二個(gè)數(shù)N（1<=N<=500）。M；當(dāng)中N表示隊(duì)伍的個(gè)數(shù)，M表示接著有M行的輸入數(shù)據(jù)。接下來的M行數(shù)據(jù)中。每行也有兩個(gè)整數(shù)P1。P2表示即P1隊(duì)贏了P2隊(duì)。

輸出

給出一個(gè)符合要求的排名。輸出時(shí)隊(duì)伍號(hào)之間有空格。最后一名后面沒有空格。

樣例輸入

15 20 15 4 15 11 15 5 1 4 1 8 1 2 3 2 3 13 2 5 2 9 2 6 6 5 10 13 12 9 4 7 5 12 8 7 5 8 9 10 9 11

樣例輸出

1 3 2 6 14 15 4 5 8 7 12 9 10 11 13

題解

拓?fù)渑判蚰０孱}，唯一可能出現(xiàn)問題的地方就是題目要求同樣拓?fù)湫虻膬蓚€(gè)編號(hào)小的要在前面，

這點(diǎn)可以通過將普通拓?fù)渑判蛑械年?duì)列改為使用優(yōu)先隊(duì)列或者堆來實(shí)現(xiàn)。

直接輸出結(jié)果

#include <iostream> #include <stdio.h> #include <string.h> #include <queue> using namespace std; const int maxn=510; int graph[maxn][maxn];//保存圖 int degree[maxn];//保存入度int main() {int n,m;while(scanf("%d%d",&n,&m)!=EOF){memset(graph,0,sizeof(graph));memset(degree,0,sizeof(degree));for(int i=0;i<m;i++){int u,v;scanf("%d%d",&u,&v);if(!graph[u][v]){graph[u][v]=1;degree[v]++;//的入度++}}priority_queue<int,vector<int>,greater<int> >q;for(int i=1;i<=n;i++)if(degree[i]==0)q.push(i);bool first=1;while(!q.empty()){int cur=q.top();q.pop();if(first){cout<<cur;first=0;}elsecout<<" "<<cur;for(int i=1;i<=n;i++){if(graph[cur][i]==1){degree[i]--;//相連的點(diǎn)的入度減1if(degree[i]==0)//假設(shè)入度為0，增加隊(duì)列q.push(i);}}}printf("\n");}return 0; }

?排序結(jié)果儲(chǔ)存在vector中

#include <iostream> #include <stdio.h> #include <string.h> #include <queue> using namespace std; const int maxn=510; int graph[maxn][maxn];//保存圖 int degree[maxn];//保存入度 vector<int> ans; int main() {int n,m;while(scanf("%d%d",&n,&m)!=EOF){memset(graph,0,sizeof(graph));memset(degree,0,sizeof(degree));for(int i=0;i<m;i++){int u,v;scanf("%d%d",&u,&v);if(!graph[u][v]){graph[u][v]=1;degree[v]++;//v入度++}}priority_queue<int,vector<int>,greater<int> >q;//較小的點(diǎn)優(yōu)先出隊(duì)for(int i=1;i<=n;i++)if(degree[i]==0)q.push(i);ans.clear();while(!q.empty()){int cur=q.top();q.pop();ans.push_back(cur);for(int i=1;i<=n;i++){if(graph[cur][i]==1){degree[i]--;//相連的點(diǎn)的入度減1if(degree[i]==0)//假設(shè)入度為0，增加隊(duì)列q.push(i);}}}for(int i=0;i<ans.size();i++){printf("%d",ans[i]);if(i==ans.size()-1) printf("\n");else printf(" ");}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的排名 拓扑排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。