给定一张包含 个顶点、 条边的有向图,请输出其拓扑序(Topological Order)。若存在多个合法序列,可输出任意一种;若图中存在有向环,无法拓扑排序,则输出 。 【名词解释】 拓扑序(Topological Order)是指有向无环图(DAG)的所有顶点的一个线性排列(记为 ),满足对于图中任意一条从顶点 到顶点 的有向边,在拓扑序中, 必须出现在 的前面。即,如果存在边 ,则在排列中 的索引 必须小于 的索引 。
输入描述:
第一行输入两个整数 —— 顶点数与边数。 接下来 行,每行输入两个整数 ,表示一条从 指向 的有向边。
输出描述:
若图存在拓扑序,输出一行 个整数,按照拓扑顺序依次给出顶点编号(相邻数字以空格分隔,行尾不得有多余空格)。若图无拓扑序,输出一行一个整数 ,表示无解。
加载中...