拓扑排序详解 +模板代码详细注释（洛谷模板题）_洛谷 拓扑排序

什么是拓扑排序？

拓扑排序和平时我们说的快排、冒泡稍有不同，后者主要对数字排序前者主要是对依赖关系（或者说先后关系）进行排序，用图论的话来说就是对一个有向无环图（简称DAG）进行排序，而且必须是DAG，不是DAG就没有拓扑排序可言。而排出来的序列的顺序，我们叫拓扑序。

以下摘自百度，有一个比较好的例子：
『一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。』
我们上例子
我们来看一张DAG。

我们要求他的拓扑序：
首先我们需要记录所有节点的入度，我们的目的是找到一个没有先决条件的也就是没有箭头指向他的点。
如图寻找入度为0的点，就是①，入度为0。
把他取出来：{1}
①出来以后，注意这个时候①所指向的节点的入度已经改变了，②和③的入度各少了1，也就是每取出一个点，就要把他所有可以到达的下一个点入度减一。

此时看图寻找入度为0点，有②和③，我们取②（两个都可以，拓扑排序不一定唯一），取出来后把他所有可以到达的下一个点入度减一，④和⑤的入度减一。

接着我们取③，一样的操作。

接着取④。

以此类推。
最后得到{1 2 3 4 5 6}。

那么具体代码怎么实现不同步骤呢？（我当然不会直接一篇代码砸出来。）

1、先看我们如何存图？
邻接矩阵（数据量小时推荐）
邻接表（vector实现比较简单）
链式前向星（数据量大时推荐）

2.如何存入度？（有时候也需要存出度）
设一个$IN$数组，输入图的时候，把箭头指向的点的入度加一。

3存好图后如何开始？
第一步，找到入度为0的点：遍历所有节点，把入度为0的点放入队列中。
第二步，把队列中的点取出来（先取出来一个），遍历这个点的所能到达的下一个点，此时进行相应的操作（和题目有关），操作完之后
第三步，遍历到的点的入度减一，判断这个点入度有没有变成0，变成零的话需要进入队列。

洛谷P1113

题目看起来很长，其实都是废话，已经标好了
题目描述
John的农场在给奶牛挤奶前有很多杂务要完成，每一项杂务都需要一定的时间来完成它。比如：他们要将奶牛集合起来，将他们赶进牛棚，为奶牛清洗乳房以及一些其它工作。尽早将所有杂务完成是必要的，因为这样才有更多时间挤出更多的牛奶。当然，有些杂务必须在另一些杂务完成的情况下才能进行。比如：只有将奶牛赶进牛棚才能开始为它清洗乳房，还有在未给奶牛清洗乳房之前不能挤奶。我们把这些工作称为完成本项工作的准备工作。至少有一项杂务不要求有准备工作，这个可以最早着手完成的工作，标记为杂务1。John有需要完成的n个杂务的清单，并且这份清单是有一定顺序的，杂务k(k>1)的准备工作只可能在杂务1至k-1中。

写一个程序从1到n读入每个杂务的工作说明。计算出所有杂务都被完成的最短时间。当然互相没有关系的杂务可以同时工作，并且，你可以假定John的农场有足够多的工人来同时完成任意多项任务。

输入格式
第1行：一个整数n，必须完成的杂务的数目$(3\le n\le 10,000)$；

第22至$n+1)$行： 共有$n$行，每行有一些用1个空格隔开的整数，分别表示：

• 工作序号1至n,在输入文件中是有序的)；

• 完成工作所需要的时间$len(1\le len\le 100)$;

• 一些必须完成的准备工作，总数不超过100个，由一个数字0结束。有些杂务没有需要准备的工作只描述一个单独的0，整个输入文件中不会出现多余的空格。

输出格式
一个整数，表示完成所有杂务所需的最短时间。

输入输出样例

还不算很模板，还是要稍加思考：（有一定dp思维）
大体上，把任务网画成图，我们需要存好图，然后对他进行拓扑排序，排序的同时，需要设置一个答案数组，计算到达每个点（任务）所需的最长时间，为什么是最长时间呢，首先，到达某个点的时间只和指向他的点有关（很重要），比如我们完成任务5,需要先完成任务2和任务4，此时完成任务5的时间就只和任务2和任务4有关系了，此时假设做到并完成任务$2$需要$7h$,做到并完成任务$4$需要$11h$,那么做完任务5(假设任务5本身要$1h$)的时间一定是$11h+5h=16h$,因为就算任务2做完了，也要等任务4，所以要找最长的时间。

#include<iostream>//拓扑排序
#include<vector>
#include<queue>
using namespace std;
vector < int > edge[100005];//vactor存邻接表
int dp[100005],t[100005],ins[100005];
int main()
{
    int n,x,y;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>t[i];
        cin>>y;
        while(y){
            edge[y].push_back(x);//y->x的方向
            ins[x]++;//x入度加一
            cin>>y;
        }
    }
    queue <int >Q;
    for(int i=1;i<=n;i++){
        if(!ins[i]){
            Q.push(i);//第一步，遍历所有点，把入度为0的加入队列
            dp[i]=t[i];
        }
    }
    while(!Q.empty()){
        int p=Q.front();//第二步，取出点
        Q.pop();//取出来之后就不需要他了
        for(int i=0;i<edge[p].size();i++){
            int u=edge[p][i];//遍历p的下一个节点
            dp[u]=max(dp[u],dp[p]+t[u]);//我们需要时间最长的那个，所以是max
            ins[u]--;//第三步，入度减一
            if(!ins[u])Q.push(u);//如果入度为0，加入队列
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,dp[i]);//dp[n]不一定是最后才完成的任务，要找最大值
    }//有可能完成任务n的时候，因为前面的某个任务时间长，画样例的图，去掉几条边就能看出来了
    cout<<ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42