acwing 848 有向图的拓扑序列

输入样例：
3 3
1 2
2 3
1 3
输出样例：
1 2 3

#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);
            break;
        }
    }

    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;
}


作者：defddr
链接：https://www.acwing.com/solution/acwing/content/4196/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。