3857: 寻找所有路径

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：18 解决：9

题目描述

给定一个有 n 个节点的有向无环图（DAG），节点编号从 0 到 n−1 。
图的边由输入给出。请你找出所有从节点 0 到节点 n−1 的路径，并按字典序输出。
注意：
  • 输入保证图是有向无环图。
  • 输出时，每条路径上的节点编号用空格隔开。
  • 多条路径之间按字典序排列（即路径上第一个不同的节点编号较小的排在前面）

输入

  1. 第一行包含两个整数 n 和 m ，分别表示节点数量和边的数量。
  2. 接下来 m 行，每行包含两个整数 u 和 v ，表示存在一条从节点 u 指向节点 v 的有向边。

输出

输出若干行，每行代表一条从 0 到 n−1 的有效路径。
路径上的节点编号用空格分隔。
如果不存在任何路径，则不输出任何内容。

样例输入 复制 

4 4
0 1
0 2
1 3
2 3

样例输出 复制 

0 1 3
0 2 3

来源/分类

提交提交记录统计露一手!