提出 #47235547

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;

pair<bool, vector<int>> is_bipartite_graph(const vector<vector<int>> &G) {
    int N = G.size();
    vector<int> color(N, -1);
    auto dfs = [&](auto self, int v, int c) {
        color[v] = c;
        for (auto nv : G[v]) {
            if (color[v] == color[nv]) {
                return false;
            }
            if (color[nv] < 0) {
                if (!self(self, nv, !c)) return false;
            }
        }
        return true;
    };
    bool ok = true;
    for (int v = 0; v < N; v++) {
        if (color[v] >= 0) continue;
        if (!dfs(dfs, v, 0)) ok = false;
    }
    return {ok, color};
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N);
    vector<int> A(M), B(M);
    for (int i = 0; i < M; i++) {
        cin >> A[i];
        A[i]--;
    }
    for (int i = 0; i < M; i++) {
        cin >> B[i];
        B[i]--;
    }
    for (int i = 0; i < M; i++) {
        G[A[i]].push_back(B[i]);
        G[B[i]].push_back(A[i]);
    }
    auto ans = is_bipartite_graph(G);
    cout << (ans.first ? "Yes" : "No") << endl;
    return 0;
}

提出情報

ジャッジ結果