算法

拓扑排序

时间复杂度 O(n+m)O(n+m), nn 表示点数，mm 表示边数

bool topsort()
{
    int hh = 0, tt = -1;

    // d[i] 存储点i的入度
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

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

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

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

思路

拓扑排序流程为BFS 流程如下
1 首先找到第一个入度为0 的点 放入待处理队列，记录答案拓扑数组中 拓扑的必要条件
2 然后从该点连接的各个点 做以下操作：
2.1 删除该边后，查看从该点连接的的点的入度
2.2 如果入度为0 那么该点放入待处理队列，记录答案拓扑数组中， 再次进行BFS 直到待处理队列为空

C++ 代码

#include <iostream>

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


using namespace std;

int n, m;
vector<vector<int>> outvec(100010, vector<int>());      //入度记录
vector<int> invec(100010, 0);;    //出度记录

int main()
{
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int start; int end;
        cin >> start >> end;
        invec[end]++;
        outvec[start].push_back(end);
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        //找到第一个入度为0的点
        if (invec[i] == 0) {
            q.push(i);
        }
    }

    vector<int>  ret;
    while (!q.empty()) {
        int idx = q.front();
        q.pop();

        ret.push_back(idx);

        //抹掉这个点的所有出度边 与入度计数
        for (auto& e : outvec[idx]) {
            if (e != -1) {
                invec[e]--; //该点入度减1

                if (invec[e] == 0) {
                    q.push(e);
                }
                e = -1;  //抹掉该边
            }
        }
    }

    if(ret.size() == n)
        for (auto& e : ret) {
            cout << e << " ";
        }
    else
        cout << -1;



    return 0;
}