题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1285
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
代码例如以下：
一、（直接法）
#include <cstdio>
#include <cstring>
#define MAXN 517
int G[MAXN][MAXN];//路径
int in_degree[MAXN];//入度
int ans[MAXN];
int n, m, x, y;
int i, j; void toposort()
{
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
if(G[i][j])
{
in_degree[j]++;
}
}
}
for(i = 1; i <= n; i++)//从最小的開始寻找。
{//这样保证了有多个答案时序号小的先输出
int k = 1;
while(in_degree[k] != 0)//寻找入度为零的点
k++;
ans[i] = k;
in_degree[k] = -1;
//更新为-1。后边检測不受影响，相当于删除节点
for(int j = 1; j <= n; j++)
{
if(G[k][j])
in_degree[j]--;//相关联的入度减1
}
}
} void init()
{
memset(in_degree,0,sizeof(in_degree));
memset(ans,0,sizeof(ans));
memset(G,0,sizeof(G));
} int main()
{
while(~scanf("%d%d",&n,&m))
{
init();
for(i = 0; i < m; i++)
{
scanf("%d%d",&x,&y);
G[x][y] = 1;
}
toposort();
for(i = 1; i < n; i++)
printf("%d ",ans[i]);
printf("%d\n",ans[n]);
}
return 0;
}
二、拓扑排序+优先队列：
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
bool map[517][517];
int in[517];
priority_queue<int,vector<int>,greater<int> > q;
void topo(int n)
{
for(int i=1;i<=n;i++)
{
if(in[i]==0)
q.push(i);
}
int c=1;
while(!q.empty())
{
int v=q.top();
q.pop();
if(c!=n)
{
cout<<v<<" ";
c++;
}
else
cout<<v<<endl;
for(int i=1;i<=n;i++)
{
if(!map[v][i])
continue;
in[i]--;
if(!in[i])
q.push(i); }
}
}
int main()
{
int n,m,i,j;
while(cin>>n>>m)
{
int k=0;
memset(map,0,sizeof map);
memset(in,0,sizeof in);
while(m--)
{
cin>>i>>j;
if(map[i][j])
continue;
map[i][j]=1;
in[j]++;
}
topo(n);
}
}
三、邻接表+拓扑排序：
①：数组式邻接表：
代码例如以下：
#include <iostream>
using namespace std;
int ind[517]; // indegree入度个数
int adj[250017]; //adjacency list邻接表位置值
int adj_next[250017];//邻接表下一指针
int tail[517]; //邻接表尾 int main()
{
int n,m,i,j,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i = 0; i <= n; i++)
{
tail[i] = -1;
adj[i] = -1;
adj_next[i] = -1;
ind[i] = 0;
}
for(i = 0; i < m; ++i)
{
scanf("%d%d",&a,&b);
int x = tail[a],flag = 0;
while(x != -1) //推断是否重边
{
if(adj[x] == b)
{
flag = 1;
break;
}
x = adj_next[x];
}
if(!flag)//关联a的邻接表
{
adj[i] = b;
adj_next[i] = tail[a];
tail[a] = i;
ind[b] ++;
}
}
for(i = 1;i <= n; i++)//找n次
{
for(j = 1;j <= n;j++)//遍历
{
if(ind[j] == 0)//当入度为0时，说明靠前
{
ind[j] = -1;//在下次寻找入度为0时跳过
if(i == 1)
printf("%d",j);
else
printf(" %d",j);
for(int k = tail[j]; k != -1; k = adj_next[k])//邻接位置入度减一
{
ind[adj[k]]--;
}
break;
}
}
}
printf("\n");
}
return 0;
}
②：结构体（链表）式邻接表：
代码例如以下：
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cstdio>
#include<queue>
#include<bitset>
using namespace std;
#define maxn 517 struct node
{
int num;
node *next;
}; node map[maxn];
int d[maxn], n; void Insert(int a, int b);
void Free();
void Topsort(); int main()
{
int m; while(cin >> n >> m)
{
int i, a, b; memset(d, 0, sizeof(d)); for(i=0; i<m; i++)
{
cin >> a >> b;
Insert(a, b);
d[b]++;
} Topsort();
Free();
} return 0;
}
void Insert(int a, int b)
{
node *newnode; newnode = (node *)malloc(sizeof(node));
newnode->num = b;
newnode->next = map[a].next;
map[a].next = newnode;
}
void Free()
{
node *cur, *old; for(int i=1; i<=n; i++)
{
cur = map[i].next;
while(cur)
{
old = cur;
cur = cur->next;
free(old);
}
map[i].next = NULL;
}
}
void Topsort()
{
priority_queue<int, vector<int>, greater<int> > que;
int nx, i;
int q[maxn]={0}, k=0;
node *cur; for(i=1; i<=n; i++)
{
if(d[i] == 0)
que.push(i);
} while(que.size())
{
nx = que.top(), que.pop();
q[k++] = nx; cur = map[nx].next;
while(cur)
{
nx = cur->num;
d[nx] -= 1; if(d[nx] == 0)
que.push(nx);
cur = cur->next;
}
} cout << q[0];
for(i=1; i<k; i++)
cout <<" "<< q[i];
cout <<endl;
}