グラフ理論に関するカテゴリーです。

AtCoder, グラフ理論, 幅優先探索, 探索

問題方針

良くある迷路の探索のアルゴリズムを使って、全探索を行います。ここでは、全ての道となっているマスから幅優先探索を行い、到達可能なマスの最短距離を求めます。

コード

 

AOJ, グラフ理論, 幅優先探索, 探索

問題方針

各生徒をノードに見立てて、隣接リストを構築します。生徒 \( i \) が所属している部活動を \( g_i \) とし、所属が未確定のときを \( g_i = 0 \) とします。生徒 \( a, b \) が同じ部活動に所 ...

AtCoder, グラフ理論, 幅優先探索, 探索

問題方針

必要な色の数は、頂点の最大次数となるので、任意の頂点から幅優先探索を行い、色を振り分けていきます。辺の色を順番に出力する必要があるので、マップを使って管理します。また、色を分けるときに使用できない色を管理するためにセットを使い ...

AtCoder, グラフ理論

問題方針

トポロジカルソートを利用するみたいです。

コード

 

AOJ, グラフ理論

問題方針

閉路のない有効グラフに対して頂点を一列に整列させることができます。

コード

 

AtCoder, グラフ理論, 幅優先探索, 探索

問題方針

座標間の距離が与えられるので、相対的な位置が分かります。したがって、ある座標の値を \( x_i = 0 \) として、\( M \) 個の情報に誤りがあるかどうかを調べます。

グラフ

各座標をグラフの頂点として、\ ...

AtCoder, グラフ理論, 数学

問題方針

一見難しそうに見えますが、\( 300 \) 点の問題なので解法は簡単であることが予想できます。

実現不可能な整数列頂点 \( 1 \) からの距離について

頂点 \( 1 \) からの距離が与えられるので、 ...

yukicoder, グラフ理論, ダイクストラ法, 全探索, 探索

問題方針

解説を見ても良く分かりませんでした。

似たような問題で、CSA の良問があります。

コード

 

AtCoder, グラフ理論

問題方針

グラフが連結であることから、辺の数は最低でも \( N – 1\) 本必要になります。

構築できるグラフの最短距離が \( 2 \) の頂点対の個数の最大値

辺の数が \( N – 1 \) ...

AtCoder, Union Find, グラフ理論

問題方針行と列を分けて考える

グリッドの問題は行と列を分けて考えることができるかを最初に考えます。この問題も行と列を分けて考えることができます。\( i \) 行 \( j \) 列のマスを \( c(i, j) \) とします。ここで ...