ロアちゃんかわいい

競プロっぽい話がなされる駄文の掃きだめ

二部グラフ判定

おはようございます。愛と正義の侵略者です。そろそろゴールデンウィークですね。

AGC039お疲れ様でした。何も分からなかった。

Aだけ解いて水パフォ出してレートを少し上げるみたいな生活をそろそろやめたいです。まだ緑で消耗してるの?(笑)

そんなわけで少しずつ学習を進めていくべく、二部グラフについてちょっと勉強しました。

二部グラフってなに? 調べてみた!

いかがでしたか? 二部グラフというのは頂点が二つのグループに分けられ、同じグループ同士の頂点同士を繋ぐ辺が存在しないようなグラフのことなんですね!


二部グラフの応用例は広く、中々全部を網羅するのは難しそうです。

ひとまずグラフが二部グラフに出来るかの判定をする関数を書いてみました。

深さ優先探索でグラフを見ていきます。
各頂点に色を交互に(つまり同じ色が隣合わないように)割り振っていき、既に探索済みのところに当たったらその頂点の色と現在引数で持っている色との整合性が取れるかを判定します。
(色は配列に収めるようにします。)
整合性が取れるなら問題なし、取れなければ二部グラフには出来ません。

//二部グラフに出来るかを判定
//now:現在の頂点番号
//color:1か2
//colors[i]: i番目の色、1か2を入れる。初期値は0で、このときi番目は未訪問
//graph: 探索対象のグラフ。適当に構成する。
//呼び出し方はisPartited(0,1)とかでよさげ
int colors[10000];
vector<vector<int>> graph(10000);
bool isPartited(int now, int color){
    if(colors[now]){ //探索済み
        if(colors[now] != color) return false; //探索済みなら色の整合性が取れないとダメ
        else return true;
    }
    colors[now] = color;
    int g_size = graph[now].size();
    for(int next = 0; next < g_size; ++next){ //ここの処理はグラフの実装によって適当に変えます
       if(!isPartited(graph[now][next], 2-((color+1)%2))) return false; //1つでもfalseがあったら二部グラフにはならない
    }
    return true; //分岐が全てtrueならtrue
}

昨日のB問題を通す時に使ったのを元に書いたので多分バグはないと思いますが、使う人(いるのか?)は自己責任でお願いします。

グラフの構成とかは適当にやってください。僕は基本的にvector> graph(適当なサイズ)をやってここに要素を追加して隣接リストにして作っています。

しかし「そんな甘っちょろいことやってられるか!」みたいな人がいる(訳ないけど万が一いる)なら上手く実装を変更してどうぞ。

(このブログ見るの僕と同じかそれ未満の実力の人ぐらいだと思うので、そんな人はいないとは思うんですが)


そういえばグラフの直径を求める時にワーシャルフロイド法を使えるのは知りませんでした。考えたら当たり前なんですが……><

いやもっと精進しないといけない。某に「精進グラフが対数になってるよ?(笑)怠惰くん大丈夫?(笑)あっこるぼーくんだった(笑)」とか煽られました。

ではおやすみなさい。