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

AtCoder, Union Find

問題方針

区間和のような情報が必要なので、セグメント木を使います。\( 1 \) 文字目から \( i \) 文字目までの文字の種類を \( 2 \) 進数を用いて表現します。これは、\( 26 \) ビットで表現できます。これをセグメ ...

AtCoder, Union Find

問題方針

まず初めに、友達関係の Union-Find を作成します。このとき、人 \( i \) の友達の数を \( f_i \) として数えます。次に、人 \( i \) のブロック人数を \( b_i \) と、人 \( i \) ...

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

問題方針

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

コード

 

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

問題方針

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

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

問題方針

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

AtCoder, グラフ理論

問題方針

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

コード

 

AOJ, グラフ理論

問題方針

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

コード

 

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

問題方針

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

グラフ

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

AtCoder, グラフ理論, 数学

問題方針

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

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

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

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

問題方針

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

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

コード