关于连接的图论难题？

-5

你有一个图形n节点（编号1-n）和m边缘。您逐个删除所有节点，并在每一步检查图形是否完全连接（通过打印“连接”或不是）。给出要删除的节点的顺序。关于连接的图论难题？

例如，

Ñ = 4和米 = 3 给出的边缘是：1 - 2,2 - 3,3 - 4 移除顺序是：3，4， 1，2

节点编号为1-N，所以在这种情况下，节点1，2，3，4，

最初，图形连接，所以你打印出：

连接

您首先删除节点3.现在图形已断开，因为节点4是孤立的。

断开

然后删除节点4.现在的曲线仅由节点1和2，它们连接的。

连接

然后删除节点1.图形仍然被认为是连接;只有一个节点。

连接

然后删除节点2，已经没有什么东西。

示例代码会有帮助，最好是java或C++。我尝试过使用BFS和DFS，但它们太慢了。什么是最有效的方法来做到这一点？

2016-04-02 Bob Billy

向任何人投诉我的所有问题：为什么？ –

停止复制/粘贴某人要求您解决的问题，尝试回答它们，并且如果您无法向我们展示您失败的位置。它就是这样，而不是“我们做你的工作”。 – FiReTiTi

我相信我已经告诉你我失败的地方。我说过我使用过BFS和DFS，但他们太慢了。我只想知道这样做的最有效方法是什么。 –

尝试按相反顺序工作。

逐个添加边，并使用disjoint set data structure来查找该集何时连接。

2016-04-02 21:32:08

你会推荐哪种数据结构？我使用Java编写BTW –

我已经使用了过去在维基百科页面上描述的那个，并且发现它非常有效。这只是几行，所以应该用任何语言工作。 –

回答