グラフ理論

問題方針領域の作成

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

問題方針

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

コード ...

問題方針

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

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

問題方針

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

問題方針

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

コード#include <bits/stdc++.h>usi ...

問題方針

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

問題方針

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

問題方針

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

コード#include <bits/stdc++.h>using namespace std;typedef long long ll;int main() { in ...

問題方針

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

コード#include <bits/stdc++.h>using namespace std;typedef long long ll;in ...

問題方針

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

グラフ

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