[ABC327] D - Good Tuple Problem
考察
1. 二部グラフが作れるかどうかを聞かれているので、判定をしたい。
2. 普通にグラフを張る。
3. 頂点0からdfsをスタート。スタートの色は0で固定する。
4. 自分が0なら、1手先の色は1に。次は0に。を進めていく。矛盾があればNo
5. スタートする頂点をNまで確認。スタートの色が定まっているならスルー。矛盾があればNo
6. 矛盾がなければYes
実装
int main() {
cincout();
ll N, M;
cin >> N >> M;
// グラフをはる
vector<ll> G[N];
vector<ll> A, B;
rep(i, M) {
ll a;
cin >> a;
--a;
A.push_back(a);
}
rep(i, M) {
ll b;
cin >> b;
--b;
B.push_back(b);
}
rep(i, M){
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
}
// 色をぬる
vector<ll> col(N, -1);
function <void(ll)> dfs = [&](ll v){
for(auto u : G[v]){
if (col[u] == -1){
col[u] = col[v] ^ 1;
dfs(u);
}
else if(col[v] == col[u]){ // 矛盾があればNo
cout << "No" << endl;
exit(0);
}
}
};
rep(i, N){
if (col[i] == -1){
col[i] = 0;
dfs(i);
}
}
// 矛盾がなければYes
cout << "Yes" << endl;
}