拓补排序

拓扑排序（Topological Sorting）是对有向无环图的一种排序方法，它将图中的节点按照某种顺序排列，使得对于图中的每一条边 $(u,v)$，节点 $u$ 总是出现在节点 $v$ 之前

算法流程：

• 计算每个节点的入度。

• 找到入度为 0 的节点，将其加入队列，并将其从图中移除（即移除以该节点为起点的边），同时更新相邻节点的入度。

• 重复上述步骤，直到所有节点都被处理。如果图中还有节点未被处理且不存在入度为 0 的节点，说明图中有环。

模板1：

int in[N]; // in[i] 节点 i 的入度
int path[N];

bool topsort(){
    queue<int> q;
    int cnt = 0;

    for(int i = 1; i <= n; i ++){
        if(d[i] == 0){ // 入度为 0
            q.push(i);
            res[cnt ++] = i;
        }
    }

    while(q.size()){
        int t = q.front();
        q.pop();

        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            d[j] --;
            if(d[j] == 0){
                q.push(j);
                res[cnt ++] = j;
            }
        }
    }
    return cnt == n; // 如果所有点都入队了，说明存在拓补序列；反之不存在
}

模板2：数组模拟

int in[N];

bool topsort(){
    int hh = 0, tt = -1; // 数组模拟队列

    for (int i = 1; i <= n; i ++ )
        if(d[i] == 0) q[++ tt] = i;

    while(hh <= tt){
        int t = q[hh ++];

        for (int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            d[j] --;
            if(d[j] == 0) q[ ++ tt] = j;
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}