对一个==有向无环图(Directed Acyclic Graph简称DAG)==G进行拓扑排序，是将G中所有顶点排成一个线性序列， 使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。 通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。 简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
比如说给定若干个两个元素之间的大小关系，要转换成所有元素的总体大小关系，就可以用 拓扑排序 来处理
下面给出的例题就是这个样子
关于拓扑排序还有一种用法->判断给定的有向图中是否存在环
下面来说明一下拓扑排序的相关步骤：
（默认已经将图存好）首先统计所有点的入度，然后将所有点入度为0的所有点放进队列（根据题目特殊要求也可以使用优先队列）
然后采取像BFS那样的方式，当队列非空的时候，始终取队列头端的一个元素，并将这个元素记录下来之后pop掉，把这个点（比如说是点P）放进用来存储 拓扑排序 的不定长数组vector中，然后遍历和这个点相连的所有点，并将与点P相连的所有点的入度减少1（换句话说讲点P去掉之后，他的指向关系就会消失，并且以他为起点的所有点的入度都会减小1），如果这个点的入度刚好为0，那么正好可以将这个点继续放到队列中，如此反复
伪代码如下
void top_sort(){ for(int i=1;i<=n;i++){ if(入度为0) que.push(i); } while(que.size()){ int top = que.top()/que.front(); que.pop(); vet.push_back(这个点->top); for(int i=1;i<=n;i++){///在数据范围足够小的情况下可以直接采取二维数组存图 /// gra[i][j] == 1表示有一条从i指向j的边，反之没有 if(相连的点){ deg[i]--; if(deg[i] == 0) que.push(i); } } } }
下面是比较常用的小模板：
priority_queue <int, vector<int>, greater<int> >litt; int dege[507]; int n,m; int gra[507][507]; vector<int>vet; void top_sort(){ for(int i=1;i<=n;i++) { if(dege[i] == 0) litt.push(i); } while(litt.size()){ int tp = litt.top(); litt.pop(); vet.push_back(tp); for(int i=1;i<=n;i++){ if(gra[tp][i]){ dege[i] --; if(dege[i] == 0) litt.push(i); } } } }
下面来看例题：
题目描述
有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
- 注意本题为多组输入
- 本题可能出现相同的大小关系，比如2 3出现两次。那么这个时候应该进行去重处理，否则会有多余的入度被增加，导致出现错误
Main_Code():
priority_queue <int, vector<int>, greater<int> >litt; int dege[507]; int n,m; int gra[507][507]; vector<int>vet; void top_sort(){ for(int i=1;i<=n;i++) { if(dege[i] == 0) litt.push(i); } while(litt.size()){ int tp = litt.top(); litt.pop(); vet.push_back(tp); for(int i=1;i<=n;i++){ if(gra[tp][i]){ dege[i] --; if(dege[i] == 0) litt.push(i); } } } } bool vis[507]; int main() { while(cin >> n >> m){ while(litt.size()) litt.pop(); for(int i=1;i<=n;i++) vis[i] = 0; for(int i=1;i<=n;i++) dege[i] = 0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) gra[i][j] = 0; } vet.clear(); while(m --){ int a=read,b=read; if(gra[a][b] == 0) dege[b] ++;/// a > b deg[b] ++; gra[a][b] = 1;/// directed } top_sort(); for(int i=1;i<=n;i++){ printf("%d",vet[i-1]); if(i != n) printf(" "); } puts(""); } return 0; }/// ac_code
