http://acm.hdu.edu.cn/showproblem.php?pid=1285
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出 现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。
—————–摘自《百度百科》
简单的说,就是要求一项工程的完成时的先后序列,比如做暑假作业,先数学,再语文,最后英语,这是一种。注意拓扑排序不能有环!
排序方法:
步骤:1、找入度0的点进序列,接着去掉这个点的出边
2、再找入度0的点进序列,接着去掉这个点的出边
3、如此循环直到点都进了序列,如果同时有入度为0的点就随便进一个点到序列
上个hdu题目的解题代码:
#include <stdio.h> #include <stdlib.h> #include <string.h> int graph[505][505]; int du[505]; void topological_sort(int n) { int i,j,k,w; for (i=1; i<=n; i++) //要遍历n次 { for (j=1; j<=n; j++) //找入度为0的点 { if (du[j]==0) //找到了 { printf("%d%c",j,i==n?'\n':' '); du[j]--; //入度变-1表示去掉这个点(已经排序了) k = j; //记录 break; } } for (w=1; w<=n; w++) //找和k点邻接的点(被k打败过的对手) { if (graph[k][w]==1) { // graph[k][w] = 0; //标记为找过了 du[w]--; //入度-1(表示把k的出度/出边去光了) } } } } int main() { int n,m,x,y; while (scanf("%d%d",&n,&m)==2) { memset(graph,0,sizeof(graph)); memset(du,0,sizeof(du)); while (m--) { scanf("%d%d",&x,&y); if (graph[x][y]==0) //x打败y { graph[x][y] = 1; //在邻接矩阵中记录为1表示不能被同一个对手重复打败 du[y]++; //y被打败过就入度+1 } } topological_sort(n); } return 0; }