题解 | 二分图判定

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using LL = long long;
constexpr int N = 2e5 + 5;
int n, m;
int cor[N];
vector<int> g[N];

bool dfs(int u, int c) {
    cor[u] = c;
    for (auto v: g[u]) {
        if ((!cor[v] && !dfs(v, c ^ 3)) || cor[v] == c)return false;
    }
    return true;
}

void solve() {
    cin >> n >> m;
    for (int i = 1, x, y; i <= m; ++i)cin >> x >> y, g[x].emplace_back(y), g[y].emplace_back(x);
    for (int i = 1; i <= n; ++i) {
        if (!cor[i] && !dfs(i, 1)) {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int tt = 1;
    //    cin >> tt;
    while (tt--) solve();
}