「グラフ」の基礎問題！ グラフを知らなくても解ける。 問題へのリンク 問題概要 個の都市 () があり、 本の道路がある。 番目の道路は、都市 と都市 を結んでいる。同じ 2 つの都市を結ぶ道路は、1 本とは限らない。 各都市から他の都市に向けて、何本の道…

面白い問題だった。 問題へのリンク 問題概要 下の図のような木を「ユ木」と呼ぶ（正式な定義は問題文参照）。 頂点数 の木が与えられ、いくつかの頂点を削除して「ユ木」にしたい。削除する頂点の個数の最小値を求めよ。 制約 考えたこと 与えられた木にお…

evima さんの別解で解いた。 問題へのリンク 問題概要 頂点数 の単純な木が与えられる。この木に辺を 1 本追加して得られるグラフのうち、次の条件を満たすものの個数を求めよ。 単純グラフである サイクルをちょうど 1 つ含み、そのサイクルに含まれる頂点…

次数制約つきのグラフを構築するためには、次数の大きいところから Greedy というよく知られた問題！ 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 以下の条件を満たすような、頂点数 のグラフが存在するかどうかを判定せよ。 単純…

想定解法が天才的に思えたとしても、愚直なグラフ探索でも解ける！ 時には腕力で頑張るのも有効！ 問題へのリンク 問題概要 競技プログラマ がいる。 組については、どちらが強いかが分かっている。具体的には に対して は、 より強い ということが分かって…