關於連接的圖論難題？

-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 –

我已經使用了過去在維基百科頁面上描述的那個，並且發現它非常有效。這只是幾行，所以應該用任何語言工作。 –

回答