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

AtCoder, Union Find, 実装

問題方針

生徒がどの集団に属するかは Union-Find で管理し、ある集団における各クラスの人数はマップを用いて管理します。ある集団をマージするとき、各クラスの情報も更新する必要があるので、人数の少ない集団の各クラスの人数を人数の多 ...

AtCoder, Union Find, 数え上げ

問題方針

例えば、\( 1 \) 行目と \( 2 \) 行目が交換可能であり、\( 1 \) 行目と \( 3 \) 行目が交換可能であるとき、各 \( 1, 2, 3 \) 行の順番を任意に並び替えることができます。したがって列に対 ...

AtCoder, Union Find

問題方針

連結されている頂点の集合は、任意の頂点 \( 2 \) 組に対して操作を行うことができます。これは、隣接している頂点を適切に選ぶことで達成できます。したがって、ある連結されている頂点の集合の \( a_i \) と \( b_ ...

AtCoder, bitDP, グラフ理論

問題方針

いわゆる巡回セールスマン問題というやつです。

\( g(i, j)\) を都市 \( i \) から都市 \( j \) に移動するときのコストとします。\( d(i, j) \) を訪れた都市の状態 \( i \ ...

AtCoder, Union Find, 数え上げ

問題方針照らされるマスについて

散らかっていないマス \( (i, j) \)に照明を置いたとき、水平方向を照らすマスの数を \( a(i, j) \) とし、垂直方向を照らすマスの数を \( b(i, j) \) とします。このとき、 ...

AtCoder, Union Find, 幅優先探索

問題方針Union-Find

グラフが連結かどうかを調べるには Union-Find を使えば良いので、ライブラリの dsu を使います。グループの数から \( 1 \) を引いた値が必要な道路の本数です。グループの数は、groups( ...

AtCoder, Union Find, 幅優先探索

問題方針

友達同士のグループの人数の最大値の分だけグループがあれば、「同じグループの中に友達がいない」という状況がつくれます。したがって、連結成分の最大値を求めます。これは、幅優先探索や Union-Find を使うことで求めることがで ...

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

問題方針領域の作成

徒歩で行くことができるマスをグループ化し、IDを振ります。マス \( (i, j) \) の ID が \( 0\) であることを \( G(i, j) = 0 \) と表し、そのマスから徒歩でいけるマスの ID は ...

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

問題方針

幅優先探索で迷路を解くような感じで考えます。始点 \( 1 \) から幅優先探索を行い、到達した部屋の道しるべは、直前に来た部屋となります。隣接リストを作成し、到達した部屋のフラグを管理することで探索を行います。

コード ...

AtCoder, グラフ理論

問題方針

配列は \( 0 \) を基準として考えます。

閉路を構築する問題です。頂点 \( 1 \) から出発してループになっている道を見つけるには、頂点に訪れた回数を数えれば良いです。\( 2 \) 回以上訪れた頂点の集 ...