はむ吉（のんびり）の練習ノート

プログラミングとことばに関する話題を中心に，思いついたこと，試してみたこと，学んだことを，覚え書きを兼ねてまとめます．その際に役立った，技術書，参考書，辞書，機器などの紹介も行います．

yukicoder No.416 旅行会社：解き方とC++によるその実装

yukicoder 競技プログラミング プログラミング グラフ理論

この記事では、先日行われたyukicoderのコンテストで出題された、No.416 旅行会社 - yukicoderという問題の解き方とその実装を、学習の記録も兼ねて示します。コンテスト中にはこの問題を解けなかったのですが、ほかの方が書かれた解説等を踏まえて、ようやく理解できました。

問題の趣旨

無向グラフG=(V, E)が与えられる。時刻i\:(i = 1, 2, \cdots, Q)に辺e_i \in Eが除去される。各頂点について、頂点1からの道が一つも存在しなくなる時刻を求めよ。

解き方

除去されるQ本の辺(e_1, e_2, \cdots, e_Q)からなる集合をE'とし、最後まで除去されない辺からなる集合をE_0 = E \setminus E'とします。すると、無向グラフG_0 = (V, E_0)に、Q本の辺e_Q, e_{Q - 1}, \cdots, e_1をこの順に追加していくという問題を考えればよいことになります。辺の追加と道の有無を調べる際には、素集合データ構造、すなわちいわゆるUnion Findを使うと便利です。本問の場合には、ある頂点が属する連結成分を構成する頂点を列挙する必要があるので、その機能を追加します。具体的な処理の流れは、以下のソースコードにコメントとして記しています。

実装

C++による実装を次に示します。ここでは、添え字を1始まりから0始まりに変換しています。なお、PyPy 3でも同様のコードを書きましたが、TLEを解消できませんでした。

参考

次のページが、とても勉強になりました。ありがとうございます。

感想

素集合データ構造に新しい機能を追加する問題は時々出るようですが、私が実際に行ったのは初めてでした。有名なデータ構造やアルゴリズムを身につけるだけではなく、問題に応じてそれらを改造できるようにする必要もあると感じました。