各頂点について、頂点1からの道が一つも存在しなくなる時刻を求めよ。この順に追加していくという問題を考えればよいことになります。Findを使うと便利です。本問の場合には、ある頂点が属する連結成分を構成する頂点を列挙する必要があるので、その機能を追加します。具体的な処理の流れは、以下のソースコードにコメントとして記しています。実装C++による実装を次に示します。ここでは、添え字を1始まりから0始まりに変換しています。3でも同様のコードを書きましたが、TLEを解消できませんでした。次のページが、とても勉強になりました。ありがとうございます。素集合データ構造に新しい機能を追加する問題は時々出るようですが、私が実際に行ったのは初めてでした。有名なデータ構造やアルゴリズムを身につけるだけではなく、問題に応じてそれらを改造できるようにする必要もあると感じました。(1)月別アーカイブはてなブログをはじめよう!hamukichi_nbrさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。