0

最初: 私はそれがプログラミング コンテストの一部であることを認めます (勝つための賭け金などは何もありません)。

問題を読んで次のアルゴリズムを試した後、私は次の結論に達しました。

n頂点の無向連結グラフが与えられた場合、

count = 0
For i=1 to n:
  remove(ith vertex)
  check for connectivity of graph with remaining vertices
  if connected 
    then increment count
  attach the removed vertex back
print count

私はこれを 2 つの方法で実装しました: (1) DFS (2) Disjoint-Set Union ですが、どのアルゴリズムも AC を得るのに十分効率的ではありません。そうするためのさらに良い方法はありますか？詳細な説明は必要ありません。いくつかの単語で十分です。残りは、理解するか、試して死ぬでしょう:p。ありがとう！

4

2 に答える 2

5

削除するとグラフが切断される頂点は、アーティキュレーション ポイントと呼ばれます。グラフ内のすべての関節点は、線形時間で見つけることができます。

于 2013-04-24T16:03:19.887 に答える