拓扑排序

简介

拓扑排序就是…

实现

queue<int> Q; int in[maxn]; 
void topsort() {
    for (int i = 1; i <= n; ++i) if (!in[i]) Q.push(i);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to;
            if (--in[v] == 0) Q.push(v);
        }
    }
}

性质

1. 反图的一个拓扑序反过来是原图的一个拓扑序，且一一对应

变种

1. 求字典序最小的拓扑序

   将 queue 改成 priority_queue 即可

2. 求在 $1$ 出现位置尽量靠前的情况下，$2$ 的位置最靠前，以此类推的拓扑序

   我们考虑首先肯定要将反图中能到 $1$ 的点所有点先取出来，然后对于这些点以及它们之间的边要做同样的操作

   我们发现实际上这东西就是求反图最大字典序

   Luogu P3243 [HNOI2015]菜肴制作

例题

1. 简要题意：给定一个 $n$ 个点 $m$ 条边的有向图，现在需要改变某些边的方向，使得原图变成有向无环图，求一个改变边的方案，使得被改变的边的边权最大值最小

   $n,m\le 10^5$

   简要题解：首先我们考虑二分，然后就是判断在只改变 $[1,mid]$ 的边的方向时能否将原图变成一个有向无环图

   注意到我们只需要保证 $[mid+1,r]$ 的边无环，即能够拓扑排序即可，因为 $[1,mid]$ 的方向只需要按照 $[mid+1,r]$ 的边拓扑排序得到的拓扑序由小向大连接即可

   CF 1100E Andrew and Taxi

2. 简要题意：给定一个 $n$ 个点 $m$ 条边的有向图，问是否可以删除至多一条边，使得原图变成有向无环图

   $n\le 500,m\le 10^5$

   简要题解：第一想法肯定是枚举删那条边，然后拓扑排序，然而这样复杂度就炸了

   注意到拓扑排序中一条边只有它的终点有用，所以我们只需要枚举那个点的入度减 $1$ 即可

   时间复杂度 $O(nm)$

   CF 915D Almost Acyclic Graph

3. 简要题意：给定一个 $n$ 个点 $m$ 条边的有向无环图，求一个特殊的拓扑序，满足 $1$ 出现的位置尽量靠前，在满足这个条件的情况下，$2$ 出现的位置尽量靠前，然后是 $3$，依次类推

   $n,m\le 10^5$

   简要题解：我们考虑原图中 $1$ 尽早出现等价于反图中 $1$ 最晚出现

   所以我们考虑将图反向，然后我们一直进行拓扑排序的操作直到将除了 $1$ 以外的其它能弹出的点都弹出

   这是 $1$ 的最晚出现位置，也是原图中 $1$ 的最早出现位置

   我们对于之前出队的元素和现在在队中元素分别进行对应操作

   能够发现我们每次让反图中最大的元素出队可以完成上述操作

   Luogu P3243 [HNOI2015]菜肴制作