本题是模板题：拓扑排序。

拓扑序是有向无环图（DAG）的一种线性排列，满足：
对于图中任意一条有向边 ，在拓扑序列中， 必须出现在 之前。

举例说明

若课程依赖关系为：

  • 学「机器学习」前必须先学「线性代数」
  • 学「线性代数」前必须先学「微积分」

则合法拓扑序为：微积分 → 线性代数 → 机器学习。

如果存在循环依赖（如 A→B→C→A），则无法拓扑排序。

核心思路

Kahn 算法（基于入度） 我们采用经典的 Kahn 算法，核心思想是：

不断找出“当前没有依赖”的顶点（入度为 0）

算法步骤

  1. 构建邻接表 graph 和 入度数组 indegree
  2. 初始化队列：将所有入度为 0 的顶点加入双端队列（或普通队列）
  3. 循环处理：
    • 取出队首顶点 ，加入拓扑序列
    • 遍历 的所有邻居 ：
      • 将 的入度减 1（因为 已被移除）
      • 若 的入度变为 0，将其加入队列
  4. 判断是否有环：
    • 若最终拓扑序列长度 小于 ，说明有顶点未被访问 → 存在环 → 输出 -1

正确性分析

  • 入度为 0 的顶点没有任何前置依赖，可以安全地放在当前序列最前面。
  • 每次移除一个顶点，相当于“完成一个任务”，解除它对后续任务的限制。
  • 如果图中有环，则环内所有顶点的入度永远不会降为 0，因此无法被加入序列。

该算法天然支持多起点、多路径、汇合结构，不要求图是树！

复杂度分析

  • 时间复杂度：
    • 每个顶点入队/出队一次（）
    • 每条边被访问一次（）
  • 空间复杂度：
    • 邻接表存储图（）
    • 入度数组、队列、结果数组（）

完全满足题目约束 。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,m;cin>>n>>m;
    vector graph(n+1,vector<int>());//邻接表
    vector<int>indegree(n+1,0);//入度表
    vector<int>topo_order;//拓扑排序表
    for(int i=0;i<m;i++){//构建邻接表
        int u,v;cin>>u>>v;
        graph[u].push_back(v);
        indegree[v]++;
    }
    deque<int>dq;//图遍历队列
    for(int i=1;i<=n;i++){//初始化队列
        if(indegree[i]==0)dq.push_back(i);
    }

    while(!dq.empty()){
        int u=dq.front();
        dq.pop_front();
        topo_order.push_back(u);
        for(auto& v:graph[u]){
            indegree[v]--;
            if(indegree[v]==0)dq.push_back(v);
        }
    }
    bool first=true;//控一下空格问题
    if(topo_order.size()<n)cout<<-1;//有环
    else{
        for(auto &num:topo_order){
            if(first){
                cout<<num;
                first=false;
            }
            else cout<<" "<<num;
        }
    }
}