atcoder https://blog.hatena.ne.jp/atcoder/ AtCoderInfo https://info.atcoder.jp/ グラフ理論 トーナメント 強連結成分 ソート ハミルトンパス ハミルトンサイクル 解説動画はこちらです． 1. 概要 任意の相異なる $2$ 頂点 $u,v$ について，$u\to v$ または $v\to u$ のどちらか一方が必ず存在するような単純有向グラフをトーナメントといいます．これは $N$ 人が総当たり戦をしたときの勝敗を，「勝った人から負けた人へ辺を張る」ことで表したものだと考えることができます． 定義は非常に簡潔ですが，トーナメントには一般の有向グラフには見られない強い構造が現れます．例えば，強連結成分同士の間には自然な順序があり，各頂点の入次数だけから強連結成分分解が決定できてしまいます．またトーナメントにはハミルトンパスが必ず存在します． 本記事ではこの… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Ftournament" title="トーナメント - AtCoderInfo" 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.user.blog.st-hatena.com/default_entry_og_image/158934417/1702097020779738 Hatena Blog https://hatena.blog 2026-04-10 14:09:37 rich https://info.atcoder.jp/entry/algorithm_lectures/tournament 1.0 100%