DAG拓扑排序

引入

小学奥数类型题。

沏茶过程

（烧水壶） 到 （接水） 到 （烧水 洗茶杯 找茶叶）（并行） 到 （沏茶）

即有先后顺序的流程，且必须所有步骤都能执行。

概述

• 拓扑排序是对DAG（有向无环图）的顶点进行的一种线性排序，排序序列中每个顶点都会且仅会出现一次，且对于所有有向边 \(u\rightarrow v\)，排序完后 \(u\) 都在 \(v\) 的后面。
• 如果图中存在环，就不能进行拓扑排序。
• 一个有向无环图可能有多种排序结果。
  • 对于 \(n\) 个顶点的有向无环图：
    • 最少存在 \(1\) 种合法的拓扑序列。
      • 即该图为一条直线。
    • 最多存在 \(n!\) 钟合法的拓扑序列。
      • 即该图为散点，无边。

流程

• 在拓扑排序中，用 \(L\) 记录到目前为止的拓扑序列，用集合 \(S\) 记录所有不在 \(L\) 中入度为 \(0\) 的顶点。
• 步骤执行
  • 首先遍历整张图上的顶点，如果一个顶点入度为 \(0\)，将它加入 \(S\)。
  • 当 \(S\) 不为空时：
    • 在 \(S\) 中任取一个顶点 \(x\)，将 \(x\) 加入到 \(L\) 的队尾，并把 \(x\) 从 \(S\) 中删去。
    • 遍历从 \(x\) 出发的边 \(x\rightarrow y\)，删除。如果 \(y\) 的入度变为 \(0\)，则将其加入 \(S\) 中。
  • 循环结束时：
    • 如果所有点都加入了 \(L\)，那么我们就找到了一个合法的拓扑序列。
    • 如果有点不在 \(L\) 中，证明该图有环。
• \(L,S\) 用同一个队列维护。
• 时间复杂度 \(\operatorname O(n + m)\)

代码

vector<int> edge[N + 1];
int n, m, q[N + 1], d[N + 1]//q为队列，d为入度;

void topoSort()
{
	int front = 1, rear = 0;
    for (int i = 1; i <= n; i++)
    {
		if (!d[i]) q[++rear] = i;
        while(front <= rear)
        {
            int x = q[front];
            ++front;
            for (auto to : edge[x])
            {
                if (--d[to] == 0)//没必要真的删边，维护d数组即可
                {
					q[++rear] = to;
                }
            }
        }
    }
    if (rear == n)
    {
		printf("合法");
    }
    else
    {
		printf("不合法");
    }
}