c# - 无向图逐渐删除所有点但不创建2个图

Question

城市通过电话线连接并进行通信。我想摧毁所有的城市，但又不想过早地惊动另一个城市，所以我在摧毁城镇之前断开了电线。我不想断开用作两个城市之间桥梁的城镇。

如果我没记错的话，它是无向图。但我不明白如何检查我可以删除哪些城市，哪些不能。我查看了 Tarjan 的算法，但我不明白。

这是测试输入：

15 19 <- Number of cities and number of connections
1 2 <- Start of connections list
2 3
2 4
2 5
5 6
5 7
7 8
8 9
5 9
1 9
10 11
1 11
11 12
12 13
13 14
1 14
9 14
13 15
9 15

输出可以是这样的：

10 12 6 3 14 11 4 13 15 8 9 7 5 2 1

Answer 1

我想我解决了。它只需要做 DFS 算法。在那个结果之后，我需要的是反向 DFS 输出。

例如，如果 DFS 输出为 3,5,4,1,2 结果为 2,1,4,5,3

这是 C# 的 DFS：http ://www.koderdojo.com/blog/depth-first-search-algorithm-in-csharp-and-net-core