1.定义
对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
举例：
我们起床穿裤子和鞋子时，相信大部分人的顺序是这样的，先穿上内裤，然后再穿上裤子，再穿上袜子，然后才是鞋子。那么，我们把这些步骤分解：
(1)穿内裤
(2)穿裤子
(3)穿袜子
(4)穿鞋子
我们把这四个步骤，按照上述的顺序给排一下，就是所谓的拓扑排序 。
2.注意
1)只有有向无环图才存在拓扑序列;
2)对于一个DAG,可能存在多个拓扑序列;
如:
该DAG的拓扑序列为A B C D或者A C B D
而此有向图是不存在拓扑序列的，因为图中存在环路
3..拓扑序列算法思想
(1)从有向图中选取一个没有前驱(即入度为0)的顶点，并输出之;
(2)从有向图中删去此顶点以及所有以它为尾的弧;
重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。
4.代码
#include<cstdio>
#include<cstring>
int ans[][];//记录两人是否进行了比赛
int n,indegree[];//记录前驱个数
int queue[];//保存拓扑
void topsort()
{
int i,j,top,k=;
for(j=; j<n; ++j)
{
for(i=; i<=n; ++i)
{
if(indegree[i]==)//前驱为零即是当前第一名
{
top=i;
break;
}
}
queue[k++]=top;//当前第一名入队列，也可以直接输出
indegree[top]=-;//前驱数量更新为-1，避免重复入队列
for(i=; i<=n; ++i)
{
if(ans[top][i])//将前驱中含有当前第一名的前去数量减一
indegree[i]--;
}
}
for(i=; i<k-; ++i)
printf("%d ",queue[i]);
printf("%d\n",queue[n-]);
} int main()
{
int i,a,b,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(indegree,,sizeof(indegree));//数组初始化为0
memset(ans,,sizeof(ans));//数组初始化为0
for(i=; i<m; ++i)
{
scanf("%d%d",&a,&b);
if(ans[a][b]==)
{
ans[a][b]=;//记录是否进行了比赛
indegree[b]++;//记录前驱数量
}
}
topsort();
}
return ;
}