染色法判定二分图

原理

见《进阶指南》第423页。

模板题

AcWing-860-染色法判定二分图

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010;
struct edge {
    int to, next;
};
edge e[2 * N];
int idx, head[N];
int n, m;
bool flag = true;
int c[N];

void add_edge (int u, int v) {
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
void dfs (int cur, int color) {
    c[cur] = color;
    for (int i = head[cur]; i != -1; i = e[i].next) {
        int to = e[i].to;
        if (c[to] == color) {
            flag = false;
            return;
        }
        if (c[to] == 0) dfs(to, 3 - color);
    }
}

int main () {
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; ++ i) {
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }

    for (int i = 1; i <= n; ++ i) {
        if (c[i] == 0) {
            dfs(i, 1);
            if (flag == false) break;
        }
    }
    printf(flag ? "YES" : "NO");
    return 0;
}