python - 在 DFS 中寻找前后弧？

Question

我想编写一个程序，从节点 0 开始对每个有向图执行 DFS，并打印出遍历产生的后弧和交叉弧的总数。当可以选择白色或灰色节点时，应选择索引最低的节点。我该怎么做呢？TIA。

因此，如果这是输入：

4
1 3
2 3
0

3
1 2

1
0

输出将是：

1 0
0 1

注意：输入格式是一个或多个二合字母的序列，取自键盘 (System.in)。每个图都由一个邻接表表示。第一行是一个整数 n，表示图形的顺序。接下来是 n 个空格分隔的邻接列表，用于标记为 0 到 n - 1 的节点。这些列表是排序的。输入将由一个由一个零 (0) 组成的行终止。不应处理此行。下面的示例输入显示了两个有向图，第一个有节点集 {0,1,2,3} 和弧集{(0,1),(0,3),(1,2),(1,3)， (2,0)}，第二个有节点集{0,1,2}和弧集{(0,1),(0,2),(2,1)}。

标签： pythondepth-first-search