网站源码怎样弄成网站,工商登记网站,深喉咙企业网站生成系统,钓鱼平台设计题干#xff1a;
有N个比赛队#xff08;1N500#xff09;#xff0c;编号依次为1#xff0c;2#xff0c;3#xff0c;。。。。#xff0c;N进行比赛#xff0c;比赛结束后#xff0c;裁判委员会要将所有参赛队伍从前往后依次排名#xff0c;但现在裁判委…题干
有N个比赛队1N500编号依次为123。。。。N进行比赛比赛结束后裁判委员会要将所有参赛队伍从前往后依次排名但现在裁判委员会不能直接获得每个队的比赛成绩只知道每场比赛的结果即P1赢P2用P1P2表示排名时P1在P2之前。现在请你编程序确定排名。
Input
输入有若干组每组中的第一行为二个数N1N500M其中N表示队伍的个数M表示接着有M行的输入数据。接下来的M行数据中每行也有两个整数P1P2表示即P1队赢了P2队。
Output
给出一个符合要求的排名。输出时队伍号之间有空格最后一名后面没有空格。 其他说明符合条件的排名可能不是唯一的此时要求输出时编号小的队伍在前输入数据保证是正确的即输入数据确保一定能有一个符合要求的排名。
Sample Input
4 3
1 2
2 3
4 3
Sample Output
1 2 4 3
解题报告 拓扑排序模板。用邻接矩阵存图会超时。 AC代码
#includebits/stdc.husing namespace std;
const int MAX 500 5 ;
struct Node {int to;int w;int ne;
} e[MAX];
int in[MAX],head[MAX],ans[MAX];
int cnt 0,top 0;
priority_queueint,vectorint ,greaterint pq;
void init() {cnt 0;top 0;memset(in,0,sizeof(in));memset(head,-1,sizeof(head));while(!pq.empty() ) pq.pop();
}
void add(int u,int v,int w) {e[cnt].to v;e[cnt].w w;e[cnt].ne head[u];head[u] cnt;cnt;
}
int main()
{int n,m;int u,v;while(~scanf(%d%d,n,m) ) {init();while(m--) {scanf(%d%d,u,v);add(u,v,0);in[v];}//预处理一下pq for(int i 1; in; i) {if(in[i] 0 ) pq.push(i);}while(!pq.empty() ) {int cur pq.top();//养成习惯bfs中也是取出元素后都先给一个变量cur存着以免以后忘了pop并且新的都用new表示 pq.pop();ans[top] cur;for(int i head[cur]; i!-1; ie[i].ne) {in[e[i].to]--;if(in[e[i].to] 0) pq.push(e[i].to);} }if(top ! n ) printf(不成环\n);else {for(int i 1; itop; i) {printf(%d%c,ans[i],itop?\n: );}}}return 0 ;
}
超时代码
#includeiostream
#includecstdio
#includecstring
using namespace std;
//struct Edge {
// int to;
// int w;
// int ne;
//
//} e[5000];
int maze[505][505];
int in[505];
void init() {memset(in,0,sizeof(in));memset(maze,0,sizeof(maze) ) ;
}
int main()
{int n,m,u,v;int flag 0;while(~scanf(%d%d,n,m) ) {init();while(m--) {scanf(%d%d,u,v);maze[u][v] 1;in[v];}int cnt 0 ;while(1) {if(cnt n) break;flag 0 ;for(int i 1; in; i) {if(in[i] 0) {in[i]--;if(cnt n-1) {printf(%d\n,i);cnt;}for(int j 1; jn; j) {if(maze[i][j] 1) {flag 1;in[j]--;maze[i][j] 0;cnt;printf(%d%c,i,cntn?\n: );break;}}if(flag 1) {break;}}}}}return 0 ;}
