接続に関するグラフ理論のパズル？

Question

nノード（番号が1-n）とmのエッジがあります。すべてのノードを1つずつ削除し、各ステップで、グラフが完全に接続されているかどうかをチェックします（「接続済み」かどうかを確認してください）。除去されるべきノードの順序が与えられる。

たとえば、所与

N = 4とM = 3 エッジは、1 - 2,2 - 3,3 - 4 取り外し順序である：3、4、あなたがプリントアウトように、この場合のノードは1、2、3、4

まず、グラフは、接続されているので、図1に示すように、2つの

ノードは、1〜Nの番号が付けられ：

接続

最初にノード3を削除します。ノード4が単独であるため、グラフが切断されます。

切断

その後すぐノード4を除去グラフが接続されている唯一のノード1及び2、から構成されています。

接続

その後、グラフ1.ノードを削除まだ接続と考えられています。ノードは1つだけです。

接続

その後、あなたは何も残っはありませんノード2を削除します。

サンプルコードは、JavaまたはC++が役に立ちます。私はBFSとDFSを使ってみましたが、遅すぎました。これを行う最も効率的な方法は何ですか？

Answer 1

逆の順序で作業してください。

エッジを1つずつ追加し、disjoint set data structureを使用して、セットがいつ接続されるかを調べます。