确定比赛名次
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
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
一开始是先用邻接矩阵做 这样做思路比较简单但是数据一大的话就会爆内存 而且比起邻接表也慢了很多
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <iomanip>
#include <math.h>
#include <map>
using namespace std;
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt","w",stdout);
#define INF 0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long LL;
const int MAXN=1000+5;
int Map[MAXN][MAXN],cnt[MAXN];
int main()
{
//FIN
int N,M,x,y;
while(~scanf("%d%d",&N,&M))
{
memset(Map,0,sizeof(Map));
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=M;i++){
scanf("%d%d",&x,&y);
if(Map[y][x]==0) cnt[y]++;
Map[y][x]=1;
}
for(int i=1;i<=N;i++){
int j;
for(j=1;j<=N;j++) {if(cnt[j]==0) break;}
cnt[j]--;
if(i<N) printf("%d ",j);
else printf("%d",j);
for(int z=1;z<=N;z++){
if(Map[z][j]==1) cnt[z]--;
}
}
printf("
");
}
return 0;
}
第二种是优化过的邻接表
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <iomanip>
#include <math.h>
#include <map>
using namespace std;
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt","w",stdout);
#define INF 0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long LL;
const int MAXN=1e5+5;
/*判断一个有向图是否有环
每次删除一个入度为0的点，直到没有入度为0的点为止。
如果这时还有点没被删除，这些没被删除的点至少组成一个环；
反之如果所有点都被删除了，则有向图中一定没有环。*/
struct Edge{
int v,nxt;
}E[MAXN*2];
int Head[MAXN],erear;
int IN[MAXN]; //记录入度
int P[MAXN],sz; //打印用
void edge_init(){
erear=0;
memset(Head,-1,sizeof(Head));
memset(IN,0,sizeof(IN));
}
void edge_add(int u,int v){
E[erear].v=v;
E[erear].nxt=Head[u];
Head[u]=erear++;
}
int main()
{
//FIN
int n,m;
while(~scanf("%d%d",&n,&m))
{
edge_init(); //初始化
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
edge_add(u,v);
IN[v]++; //v的入度+1
}
sz=0;
priority_queue<int,vector<int>,greater<int> >Q; //这题要用到优先队列
for(int i=1;i<=n;i++){
if(!IN[i]) Q.push(i); //把入度为0的加入队列
}
bool sign=0; //判断是否有多个结果
while(!Q.empty()){
if(Q.size()>=2) sign=1;
int u=Q.top();
Q.pop();
P[sz++]=u; //把要打印的数加入P
for(int i=Head[u];~i;i=E[i].nxt){ //普通遍历
int v=E[i].v;
IN[v]--; //删边
if(!IN[v]) Q.push(v); //如果删边后新点入度为0加入队列
}
}
if(sz!=n){ //如果不可能的话
printf("invalid
");
return 0;
}
/*if(sign){
printf("multi ans
");
return 0;
}*/
for(int i=0;i<sz;i++){
if(i==0) printf("%d",P[i]);
else printf(" %d",P[i]);
}
printf("
");
}
return 0;
}