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

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
class Solution
{
private:
    vector<vector<int>> Graph;
    vector<int> visited;
    bool valid;
public:
    vector<int> topoSort;
    Solution(int n, vector<vector<int>>& edges)
    {
        Graph.resize(n+1);//结点个数
        visited.resize(n+1,0);
        valid = true;//默认存在合法的拓扑排序，也就是说该图是无环的有向图
        for(const auto& edge : edges)
        {//根据输入的边来建立有向图
            Graph[edge[0]].push_back(edge[1]);
        }
    }
    //通过深度优先搜索获得逆序的拓扑排序
    void dfs(int node)
    {
        if(!valid)
        {//假如已经得到该图有环，则直接return
            return;
        }
        visited[node] = 1;
 
        for(int neighbor : Graph[node])
        {//遍历结点node的所有邻居
            if(visited[neighbor] == 1)
            {//如果已经访问过邻居，说明该图有环
                valid = false;
                return;
            }
            if(visited[neighbor] == 0)
            {//如果没访问过邻居，说明该图可能无环
                dfs(neighbor);
            }
        }
        visited[node] = 2;//标记为已访问,防止重复访问
        topoSort.push_back(node);
    }
 
    void topoSorting()
    {
        for(int i = 1;i < Graph.size();++i)
        {//对所有未访问过的结点进行dfs
            if(visited[i] == 0)
            {
                dfs(i);
            }
        }
        if(!valid)
        {
            cout << -1 << endl;
            return;
        }
        reverse(topoSort.begin(), topoSort.end());
        for(int i = 0;i < topoSort.size()-1;++i)
        {//注意题目要求最后一个数字后面不能带空格！！！ 我开始的时候没看到，来回改来改去，以为自己写的有问题，结果是空格的锅，破题目😡
            cout << topoSort[i] << " ";
        }
        cout << topoSort[topoSort.size()-1];
    }
};
 
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> edges(m,vector<int>(2));
    for(auto&& edge : edges)
    {
        cin >> edge[0] >> edge[1];
    }
    Solution solution(n, edges);
 
    solution.topoSorting();
 
     
}