drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ JOI JOI本選 JOI難易度7 AtCoder AOJ グラフ DFS トポロジカルソート BFS DAG どれか1つ求める 決めてから整合性を確認する 考察：必要条件を列挙して十分性を示す queue 後退解析 【問題集】DFS・BFSのステップアップ NoviSteps1Q トポロジカルソートせよ、という問題！ 問題へのリンク 問題概要 頂点数 、辺数 の DAG (閉路のない単純有向グラフ) が与えられる。 このグラフのトポロジカルソート順を一つ求めよ。また、トポロジカルソート順が唯一かどうかを判定せよ。 制約 考えたこと まずトポロジカルソート自体は次の記事に書いた！ DFS でやるやつ qiita.com BFS でやるやつ qiita.com 一意性の方をちょっと考えてみよう！ トポロジカルソートが一意となる条件とは まずトポロジカルソートとは、下図のように、各頂点を辺の向きに沿うように一列に並べることである。 上の並び替え方は一意ではない。下図のような並… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2021%2F01%2F02%2F164800" title="JOI 本選 2007 D - 最悪の記者 (AOJ 0519) (1Q, 難易度 7) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/d/drken1215/20210102/20210102155126.png Hatena Blog https://hatena.blog 2021-01-02 16:48:00 rich https://drken1215.hatenablog.com/entry/2021/01/02/164800 1.0 100%