HDU 1285 确定比賽名次（三種模闆，用二維數組，隊列，鄰接表）

确定比賽名次

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 22252    Accepted Submission(s): 8965

Problem 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
        

  用二維數組記錄兩者之間的關系（用c++編譯錯誤用G++送出）； 代碼：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int map[510][510];//map[i][j]記錄i與j兩者之間的關系； 
int queue[510];// 
int indegree[510];//indegree[i]表示i的入度，前驅數量； 
int topo(int n)
{
	int i,j,k,t=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(indegree[j]==0)//每次找出前驅數量為0的點，即每次找到第一名； 
			{
				k=j;
				break;
			}
		}
		queue[t++]=k;
		indegree[k]=-1;//将找到的前驅數量為0的點入度設為-1； 
		for(int j=1;j<=n;j++)
		{
			if(map[k][j])
			  indegree[j]--;//第二步将前驅中與第一名有關系的點入度減1； 
		}
	}
	printf("%d",queue[0]);//輸出拓撲排序； 
	for(int i=1;i<n;i++)
	{
		printf(" %d",queue[i]);
	}
	printf("\n");
}
int main()
{
	int n,m,a,b;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(map,0,sizeof(map));
		memset(indegree,0,sizeof(indegree));
		for(int i=0;i<m;i++)
		{
			scanf("%d%d",&a,&b);
			if(map[a][b]==0)//避免重複的資料輸入； 
			{
				map[a][b]=1;//第一步記錄關系和點的前驅數量 ； 
				indegree[b]++;
			}
		}
		topo(n); 
	}
	return 0;
}
           

用隊列做：

#include<string.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
int map[510][510];
int indegree[510];
int topo(int n)
{
	int i,j;
	priority_queue<int,vector<int>,greater<int> >Q;
	for(i=1;i<=n;i++)
	{
		if(indegree[i]==0)
		Q.push(i); 
	}
	int sign=1;
	while(!Q.empty())
	{
		int top=Q.top();
		Q.pop();
		indegree[top]=-1;
		if(sign)
		   printf("%d",top);
		else
		   printf(" %d",top);
		sign=0;
		for(j=1;j<=n;j++)
		{
			if(map[top][j])
			{
				indegree[j]--;
				if(indegree[j]==0)
				  Q.push(j);
			}
		}
	}
	printf("\n");
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(map,0,sizeof(map));
		memset(indegree,0,sizeof(indegree));
		for(int i=0;i<m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			if(map[a][b]==0)
			{
				map[a][b]=map[b][a]=1;
				indegree[b]++;
			}
			  
		}
		topo(n);
	}
	return 0;
}
           

用臨界表的方法存儲關系； 代碼：

#include<stdio.h>
#include<string.h>
int head[2500];
int queue[2500];
int num;
int indegree[510];
struct node
{
	int to,next;
}a[2510];
void init()
{
	memset(head,-1,sizeof(head));
	memset(indegree,0,sizeof(indegree));
	num=0;
}
void add(int x,int y)
{
	a[num].to=y;        //或者寫成node E={y,head[x]}; 
	a[num].next=head[x];//        a[num]=E;
	head[x]=num++;
	indegree[y]++;
}
int topo(int n)
{
	int i,j,k,t=0;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(indegree[j]==0)
			{
				k=j;
				break;
			}
		}
		queue[t++]=k;
		indegree[k]=-1;
		for(j=head[k];j!=-1;j=a[j].next)
		{
			int m=a[j].to;
			indegree[m]--;
		}
	}
	printf("%d",queue[0]);
	for(int i=1;i<n;i++)
	{
		printf(" %d",queue[i]);
	}
	printf("\n");
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		init();
		for(int i=0;i<m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			add(a,b);
		}
		topo(n);
	}
	return 0;
}