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

本题可分为两部分：
1.根据输入使用邻接表建图，并将每个顶点的入度记录下来；
2.采用类似于BFS（广搜）的思想，依次遍历入度为0的顶点，并根据邻接表进行相应顶点入度的调整，最终判断是否可以得到拓扑排序并进行相应的输出。

对于第一部分，可以使用每个元素为一个数组的vector容器模拟邻接表进行建图，vector[a]所对应的数组中存储着该顶点所指向的其他顶点。之后使用一个数组inDegree记录每个顶点的入度。
对于第二部分，可以使用一个队列，初始时将所有入度为0的顶点全部入队，之后采用BFS的思想，依次取出队头元素并存入结果数组中，然后在邻接表中遍历该队头元素所指向的其他顶点，将这些顶点的入度全部减一，若减一后某顶点的入度变为0，则将该顶点进行入队操作，重复此步骤直至队列为空为止。
【需要设置一个用于判断图中是否存在环（是否可以得到拓扑序列）的计数器，在弹出队头元素后要将计数器加一，最后队列为空后，若计数器的值与顶点数相同，则说明图不存在环，可以得到拓扑序列。】

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

#define MAX 200001
using namespace std;
int main()
{
    int n, m;
    cin>>n>>m;
    vector<int> adjlist[MAX]; // 用于模拟邻接表的vector容器
    int inDegree[MAX] = {0}; // 用于记录每个顶点入度的数组，初始值全部设置为0
    int a, b;
    for(int i = 0; i < m; i++)
    {
        cin>>a>>b;
        adjlist[a].push_back(b);
        inDegree[b]++;
    }

    queue<int> que;
    for(int i = 1; i <= n; i++)
    {
        if(inDegree[i] == 0) // 将初始入度为0的顶点全部入队
        {
            que.push(i);
        }
    }
    int cnt = 0; // 用于判断图中是否存在环的计数器
    vector<int> res; // 用于存储结果序列的数组
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        res.push_back(u); // 存储结果用于输出
        for(int i = 0; i < adjlist[u].size(); i++) // 遍历该顶点指向的其他顶点
        {
            int v = adjlist[u][i];
            inDegree[v]--; // 被指向的顶点的入度减一
            if(inDegree[v] == 0) // 若顶点的入度减为0，则将其入队
            {
                que.push(v);
            }
        }
        cnt++;
    }
    if(cnt == n) // 若计数器与顶点数相同则图无环，存在拓扑序列
    {
        for(int i = 0; i < res.size(); i++)
        {
            cout<<res[i];
            if(i != res.size() - 1) // 此处注意：本题最后一个数字后不能输出多余空格，因此需要进行该判断
            {
                cout<<" ";
            }
        }
    }
    else
    {
        cout<<-1;
    }
    return 0;
}