题解 | #【模板】拓扑排序#

#include <cstddef>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define  Max 200005
struct arcNode {
    int arc;
    arcNode* next;
};
struct vexNode {
    arcNode* frist;
};
int main() {
    vector<vexNode> vex;
    vector<int> t1, t2;
    int n, m;
    cin >> n;
    cin >> m;
    //输入数据
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a;
        cin >> b;
        t1.push_back(a);
        t2.push_back(b);
    }
    //初始化邻接表，并将数据放入
    for (int i = 0; i < n; i++) {
        vexNode temp;
        //由于指针访问不对劲，放弃第一个节点
        temp.frist = new arcNode();
        temp.frist->arc=-1;
        temp.frist->next=NULL;
        vex.push_back(temp);
    }
    for (int i = 0; i < m; i++) {
        arcNode* temp = new arcNode();
        temp->arc = t2[i] - 1;
        temp->next = NULL;
        arcNode* p = vex[t1[i] - 1].frist;
        while (p->next) {
            p = p->next;
        }
        p->next = temp;
    }
    // 存放入度为0的节点的队列
    queue<int> que;
    // 存放每一个节点的入度，先进行初始化
    vector<int> du;
    for (int i = 0; i < n; i++) {
        du.push_back(0);
    }
    //计算当前顶点的入度
    for (int i = 0; i < n; i++) {
        du.push_back(0);
        arcNode* p = vex[i].frist;
        p = p->next;
        while (p) {
            du[p->arc]++;
            p = p->next;
        }
    }
    //将入度为0的顶点入队
    for (int j = 0; j < n; j++) if (du[j] == 0) que.push(j);
    // 存放可能要输出的顶点数目
    vector<int> aout;
    // 将入度为0顶点移除，并计算剩余顶点的入度
    while (!que.empty()) {
        int i = que.front();
        que.pop();
        aout.push_back(i);
        arcNode* p = vex[i].frist;
        p = p->next;
        while (p) {
            if (--du[p->arc] == 0) que.push(p->arc);
            p = p->next;
        }
    }
    // 判断处理后，入度为0的顶点是否是全部顶点，如果不是说明存在环
    if (aout.size() < n) cout << "-1" << endl;
    else {
        cout << aout[0] + 1;
        for (int i = 1; i < n; i++) {
            cout << " " << aout[i] + 1;
        }
        cout << endl;
    }
    return 0;
}