AtCoder が提供しているABC（AtCoder Beginner Contest）327 のD問題をC++とPythonで解いてみました。ABC327は、2023年11月4日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Good Tuple Problem（Difficulty : 709）
問題はリンク先をご覧ください。
二部グラフか判断することに帰着できます。AtCoder Problems による Difficulty は、709 でした。
解答案
ABC284D問題（解説記事）の問題文で二部グラフについて以下のように説明されていました。
無向グラフが二部グラフであるとは、下記の条件を満たすように各頂点を黒または白のどちらかの色で塗ることができることを言います。
https://atcoder.jp/contests/abc282/tasks/abc282_d
- 同じ色に塗られた頂点どうしを結ぶ辺は存在しない。
この問題は、（Ai, Bi）を辺としたグラフが二部グラフになれば、白の頂点を０，黒の頂点を1と考えれば、「良い数列の組」となります。
二部グラフかの判断は、DFS（深さ優先探索：Depth-First-Search）で行うグラフの探索を応用します。色を格納する配列 color を用意します。color の値は、－1:未決定、0:白、1:黒 とします。関数 dfs の戻り値は、二部グラフかどうかを返します。
関数 dfs の引数に色を表す cur_color を追加して、枝の先を反対の色で塗っていきます。もし、枝の先が同じ色であれば、二部グラフではないと判定できます。
C++ プログラム例（ABC327D）
上記で解説したように関数 dfs を実装しました。色が未決定の頂点に対して、dfs を呼び出し、二部グラフになっているか判定して、結果を出力しました。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> G;
vector<int> color;
bool dfs(int v, int cur_color)
{
color[v] = cur_color;
for (auto next_v : G[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()
{
int n, m;
cin >> n >> m;
G.resize(n + 1);
color.assign(n + 1, -1);
vector<int> a(m);
for (int i = 0; i < m; ++i) {
cin >> a[i];
}
vector<int> b(m);
for (int i = 0; i < m; ++i) {
cin >> b[i];
}
for (int i = 0; i < m; ++i) {
G[a[i]].push_back(b[i]);
G[b[i]].push_back(a[i]);
}
bool result = true;
for (int i = 1; i <= n; ++i) {
if (color[i] != -1) {
continue;
}
if (!dfs(i, 1)) {
result = false;
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC327D）
基本的な考え方はC++と同じです。関数の再帰呼び出し回数の上限を増やしています（2、4行目）。以下となります。
"""AtCoder Beginner Contest 327 D"""
import sys
sys.setrecursionlimit(10**6)
def dfs(v, cur_color):
global G, color
color[v] = cur_color
for next_v in G[v]:
if color[next_v] != -1:
if color[next_v] == cur_color:
return False
continue
if not dfs(next_v, 1 - cur_color):
return False
return True
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
G = [[] for _ in range(n + 1)]
color = [-1] * (n + 1)
for i in range(m):
G[a[i]].append(b[i])
G[b[i]].append(a[i])
result = True
for i in range(1, n + 1):
if color[i] != -1:
continue
if not dfs(i, 1):
result = False
print("Yes" if result else "No")こちらも「AC」と判定されました。
最後に
二部グラフの問題に帰着して、コンテスト中に解くことができました。類題のABC282D問題は、当時（2022年12月17日）、まったく解くことができませんでした。進歩を感じることができて良かったです。
引き続き ABC の問題を紹介していきます。
