C++ 拓扑排序算法实现及代码解析

该代码实现了拓扑排序，其运行流程如下：

初始化邻接表和计数器。
读入节点数和边数，并根据读入的边信息构造有向图，同时统计每个节点的入度。
将所有入度为0的节点入队，开始进行拓扑排序。
不断从队列中取出节点，将其所有邻接节点的入度减1。
如果某个邻接节点的入度变为0，则将其入队。
重复步骤4和步骤5，直到队列为空。
判断所有节点的入度是否都为0。如果是，则说明有拓扑序；否则，说明存在环。
如果有拓扑序，输出'Yes'；否则，输出'No'。

该代码的时间复杂度为O(n+m)，其中n为节点数，m为边数。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int N = 100010; // 用来表示节点数的最大值

int h[N], e[N], ne[N], idx;
int d[N]; // 存储每个节点的入度
int n, m; // n表示节点数，m表示边数

void add(int a, int b) // 建立有向图的邻接表
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool topsort() // 实现拓扑排序
{
    queue<int> q;
    for (int i = 1; i <= n; i ++ )
        if (!d[i]) // 将所有入度为0的节点入队
            q.push(i);

    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0) // 将与当前节点相关联的节点的入度减1
                q.push(j); // 如果减1后该节点的入度为0，则将其入队
        }
    }

    for (int i = 1; i <= n; i ++ )
        if (d[i]) // 如果还有入度不为0的节点，则说明存在环
            return false;

    return true;
}

int main()
{
    //初始化计数器，使用邻接表存储有向图
    memset(h, -1, sizeof h);
    cin >> n >> m;

    // 构造有向图
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b] ++ ;
    }

    // 判断是否有拓扑序 
    if (topsort())
        puts("Yes");
    else
        puts("No");

    return 0;
}

该代码使用邻接表来存储有向图，并通过队列来实现拓扑排序。代码首先初始化邻接表和入度数组，然后根据输入的边信息构造有向图并统计每个节点的入度。接着将所有入度为0的节点入队，并不断从队列中取出节点，将其所有邻接节点的入度减1。如果某个邻接节点的入度变为0，则将其入队。重复该过程，直到队列为空。最后判断所有节点的入度是否都为0，如果是，则说明有拓扑序；否则，说明存在环。

代码的时间复杂度为O(n+m)，其中n为节点数，m为边数。该代码对于理解和实现拓扑排序算法具有参考价值。