对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。
一个有向无环图的拓扑序列不是唯一的：
注意:
1)只有有向无环图才存在拓扑序列;
2)对于一个DAG,可能存在多个拓扑序列;
进行拓扑排序的算法并不复杂：（思想）
1）在有向图中选一个没有前驱（入度为0）的顶点且输出之
2）从图中删除该顶点及它发出的弧（这样就得到了别的入度为0的顶点）。
重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。然后输出全部顶点。
从描述上可以看出，我们需要记录每个顶点的入度，实现如下：由于没有记录入度这一信息，先要求出一个入度数组，来表示每个顶点的入度，这个入度数组还要动态更新，当一个顶点被删除后，它指向的顶点的入度都要减1.
拓扑排序可能是唯一的又有可能是不唯一的。（存在环）。。。。比如
像 3个篮球队进行比赛。 编号分别为 1 ， 2 ， 3。
1打赢了2
2打赢了3
3打赢了1。 问谁是最后的冠军。 各一胜一负你问我谁是冠军 ，这不是扯蛋嘛。 So，这是不能判断谁是冠军的， 因为这个事件存在一个 环，互相牵制，进行排序是不行产生结果的。
确定比赛名次
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 18388Accepted Submission(s): 7363
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<iostream> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<set> #include<map> #include<queue> using namespace std; #define LL long long const int INF = 1e9+7; const int VM = 503;// 点的个数 bool G[VM][VM];//图 int deg[VM];//各个顶点的入度 计数 void toposort(int n) {//拓扑排序 int k = 0; for (int i = 1; i <= n; i++) {//共进行|G.V|次操作 for (int j = 1; j <= n; j++) {//遍历所有的顶点 找入度为0的 if (deg[j]==0) {//找到 printf("%d%c", j, i == n ? '\n' : ' ');//输出 deg[j]--;//去掉这个点 让deg[j] = -1; k = j;//记录这个点 break;//跳出循环 } } for(int j = 1; j <= n; j++)//遍历所有的点 if (G[k][j] == true) {//找被此点打败过的点 G[k][j] = false;//标记为找到过 deg[j]--;//让这个点的入度-1 } } } int main() { int n, m; while (scanf("%d %d", &n, &m) == 2) {//多组输入， 获取n, m memset(G, 0, sizeof(G));//初始化 memset(deg, 0, sizeof(deg));//初始化 while (m--) { int u, v; scanf("%d %d", &u, &v);//获取 u,v u打败过v if (G[u][v] == false) {//防止重边 如果被同一个对手打败多次，也太伤v的心了 G[u][v] = true;//标记为真 deg[v]++;//v的入度++ 一杆长枪入洞了。 } } toposort(n);//调用函数 } return 0; }
此算法的时间复杂度为 O（n * n） 复杂度挺高的呢。
那我们要想办法优化啊。
#include<cstring> #include<queue> using namespace std; int ans[510][510]; int n,indegree[510]; void tuopu() { int i,j,t,top; queue<int>q; for(i=1;i<=n;++i) { if(indegree[i]==0) { q.push(i); break; }} int sign=1; while(!q.empty()) { top=q.front(); q.pop(); indegree[top]=-1; if(sign) { printf("%d",top); sign=0; } elseprintf(" %d",top); for(i=1;i<=n;++i)//注意，以当前第一名为前驱的点的前驱数量都要减少 { if(ans[top][i]==1) indegree[i]--; } for(i=1;i<=n;++i) { if(indegree[i]==0) { q.push(i); break; } } } printf("\n"); } int main() { int i,m,a,b; while(scanf("%d%d",&n,&m)!=EOF) { memset(indegree,0,sizeof(indegree)); memset(ans,0,sizeof(ans)); for(i=0;i<m;++i) { scanf("%d%d",&a,&b); if(ans[a][b]==0) { ans[a][b]=1; indegree[b]++; } } tuopu(); } return 0; }
