题解 | 【模板】图的结构Ⅲ ‖ 二分图判定：染色法

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
using namespace std;

//全局变量
int n, m;
vector<int>v;//记录每个节点被染黑还是染白或是没有染色，分别标记为1，2，0
unordered_map<int, vector<int>> um;//记录每个节点与哪些节点连接
unordered_set<int> visited;//记录已经访问的节点
string res = "YES";//结果字符串

//节点处理函数，对邻接节点染色
void process(int i) {
    vector<int>::iterator it;
    if (v.at(i) == 1) { //邻接节点染白
        for (it = um[i].begin(); it < um[i].end(); it++) {
            if (v.at(*it) == 1) {
                res = "NO";
                return;
            } else {
                v.at(*it) = 2;
            }
        }
    } else { //邻接点染黑
        for (it = um[i].begin(); it < um[i].end(); it++) {
            if (v.at(*it) == 2) {
                res = "NO";
                return;
            } else {
                v.at(*it) = 1;
            }
        }
    }
}

//深度优先遍历图
void dye(int i) {
    if (visited.count(i) ||
            res == "NO") { //已经访问或已经出现冲突发现不是二分图，返回
        return;
    }
    visited.insert(i);//访问标记
    process(i);//处理节点

    //递归遍历
    vector<int>::iterator it;
    for (it = um[i].begin(); it < um[i].end(); it++) {
        if (!visited.count(*it)) {
            dye(*it);
        }
    }
}


int main() {
    //输入数据
    cin >> n >> m;
    v.resize(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        if (um.count(u)) {
            um[u].push_back(v);
        } else {
            um[u] = {v};
        }
        if (um.count(v)) {
            um[v].push_back(u);
        } else {
            um[v] = {u};
        }
    }

    //从节点1开始对其它节点进行深度优先遍历以及染色，如果出现染色冲突则不是二分图
    v.at(1) = 1;//节点1染黑
    //深度优先遍历并染色
    dye(1);

    //打印结果
    cout << res << endl;
    return 0;
}
// 64 位输出请用 printf("%lld