AtCoder が提供しているABC（AtCoder Beginner Contest）282 のD問題をC++で解いてみました。ABC282は、2022年12月17日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Make Bipartite 2（Difficulty : 1154）
問題はリンク先をご覧ください。
二部グラフについての問題です。AtCoder Problems による Difficulty は、1154 でした。
考察
二部グラフとは
グラフは、ABC270 C問題、ABC277 C問題で取り扱いました。どちらも探索に DFS（深さ優先探索：Depth-First Search）を使いました。二部グラフについては、問題文の説明を引用します。
無向グラフが二部グラフであるとは、下記の条件を満たすように各頂点を黒または白のどちらかの色で塗ることができることを言います。
https://atcoder.jp/contests/abc282/tasks/abc282_d
- 同じ色に塗られた頂点どうしを結ぶ辺は存在しない。
最初のプログラム
グラフのデータと読み込みは、紹介した2つの問題の実装を流用しました。
探索を行う dfs で、すでに調べたかを格納する bool 型の配列 seen の変わりに、色を格納する配列 color を用意します。color の値は、－1:未決定、0:白、1:黒 とします。また、dfs の戻り値は、二部グラフかどうかを返します。
探索関数 dfs の引数に色を表す cur_color を追加して、枝の先を反対の色で塗っていきます。もし、枝の先が同じ色であれば、二部グラフではないと判定できます。
求めたい答えは、二部グラフであることを前提にすれば、
白の数 × 黒の数 ー M
となります。
上記をひとつにまとめた C++ プログラムが以下です。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
#define N 200001
vector<int> e[N];
vector<int> color(N, -1);
ull white = 0;
ull black = 0;
bool dfs(int v, int cur_color)
{
color[v] = cur_color;
if (cur_color == 0) {
++white;
} else {
++black;
}
for (auto next_v : e[v]) {
if (color[next_v] != -1) {
if (color[next_v] == cur_color) {
return false;
}
continue;
}
if (!dfs(next_v, 1 - cur_color)) {
return false;
}
}
return true;
}
int main()
{
ull n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
ull result;
if (dfs(1, 0)) {
result = white * black - m;
} else {
result = 0;
}
cout << result << endl;
return 0;
}用意されたテストパターンは50個でした。30個でAC、20個でWAと判定されました。
なぜ、正しくなかったのか？
提出してWA判定を受けて気づきましたが、連結になっている前提がありました。実際に、全体が連結ではない場合もあり得ます。
ここからは、公式解説を参考にします。
連結ではない場合、それぞれ二部グラフであれば、同じ連結成分の白同士、黒同士以外の辺を追加することができます。（絵で書けば分かります。）
式で表現します。連結成分の個数 $C$ として、それぞれの連結成分が含む白の個数を $W_i$、黒の個数を $B_i$ とすると、求める数字は以下となります。
$$\frac{N(N-1)}{2}\;-\;\sum^C_{i = 1} \left(\frac{B_i(B_i-1)}{2}
+ \frac{W_i(W_i-1)}{2} \right)\;-\;M$$
解答案
C++ プログラム例（ABC282D）
考察で導いたことを C++ プログラムに落とし込みました。探索関数 dfs は同じです。dfs の呼び出し方と、結果（result）の計算方法が異なっています。差分の背景色を変更しています。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
#define N 200001
vector<int> e[N];
vector<int> color(N, -1);
ull white = 0;
ull black = 0;
bool dfs(int v, int cur_color)
{
color[v] = cur_color;
if (cur_color == 0) {
++white;
} else {
++black;
}
for (auto next_v : e[v]) {
if (color[next_v] != -1) {
if (color[next_v] == cur_color) {
return false;
}
continue;
}
if (!dfs(next_v, 1 - cur_color)) {
return false;
}
}
return true;
}
int main()
{
ull n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
ull result = (n * (n - 1))/ 2 - m;
for (int i = 1; i <= n; ++i) {
if (color[i] == -1) {
white = 0;
black = 0;
if (dfs(i, 0)) {
result -= white * (white - 1)/ 2;
result -= black * (black - 1)/ 2;
} else {
cout << 0 << endl;
return 0;
}
}
}
cout << result << endl;
return 0;
}今回は、無事に AC（Accepted＝正しいプログラム）と判定されました。
ここまでで、かなり長くなってしまいました。Python 版の紹介を省略します。
最後に
ABC282 は、C問題の Diffculty が104で、D問題の Diffculty が 1154 でした。C問題とD問題の間に谷があるような構成となりました。前回のABC281も、同じような傾向がありましたが、今回の方が差が大きくなりました。
普通に速くプログラムが書けることと、アルゴリズムを専門的なレベルで理解する必要がある難易度との差でしょうか。わたしもこの谷間にいます。
解けない問題を、気長に理解していくことにします。
引き続き ABC の問題を紹介していきます。
