オンラインジャッジの問題を解決しようとしていました。n 個の頂点 (<=50000) の無向グラフが与えられ、最初はエッジがなく、次に m 個のエッジ (<100000) が与えられ、各追加後にブリッジの数を出力するように求められました。制限時間は2秒。私は、O(N + M) で実行される橋を見つけるアルゴリズムを知っており、単純な O(M*(N+M)) は予想どおりにタイムアウトします。誰かが適切なアルゴリズムで私を助けてくれますか?
ありがとう。
質問する
764 次
1 に答える
1
島はノードの集まりであり、橋を渡らずにあるノードから別のノードに移動できます。他のノードに接続されていない単一のノードは島です。
アイランド チェーンは、橋で接続された一連の島です。島鎖は非環式です。橋を渡って島を出ると、同じ橋を通らなければ島に戻ることはできません。これは、アイランド チェーンを構成するノードのコレクションが非循環的であると言っているのと同じではないことに注意してください。個々の島にはサイクルが含まれる場合があります。
グラフにエッジを追加するときは、次のルールに従ってチェーン、アイランド、およびブリッジを追跡します。
島をそれ自体に接続する新しいエッジが追加された場合、そのエッジはブリッジではありません。橋の総数は変わりません。
2 つのアイランドが同じアイランド チェーンの一部ではなく、それらを接続する新しいエッジが追加された場合、そのエッジはブリッジになり、2 つのアイランド チェーンは 1 つのアイランド チェーンにマージされます。
2 つのアイランドがアイランド チェーンの一部であり、それらを接続する新しいエッジが追加された場合、非環式プロパティを保持するために一部のアイランドをマージする必要があります。2 つの島を結ぶ島々 チェーンを通る道を見つけます。両端の 2 つの島を含め、このように横断したすべての島について、それらすべてを 1 つの島にマージします。この方法で渡った橋は、橋ではなくなります。
これらの手順を使用すると、エッジを追加するときに、グラフ内のブリッジの数を数え続けることができます。接続されていないノードのグラフから始めます。各ノードは、単一のノードを含む単一の島を含むアイランド チェーンです。エッジを追加するときは、上記の 3 つのルールを参照して、必要に応じてアイランドとアイランド チェーンをマージします。
島はノードの集合として表すことができ、島チェーンは島の無向非巡回グラフとして表すことができます。アルゴリズムの最もコストのかかる部分は、2 つの既存の島の間のパスを見つけることです。n直感的には、チェーン内の島の数は に比べて小さいままであり、全体の複雑さは O(m) 時間に近いままになると思います。
于 2012-07-19T16:55:23.730 に答える