染色法判断二分图

二分图：

二分图又称作二部图，指的是图中的点可以分割成两个点集，每个点集中的点之间没有边将他们相连。一个图是二分图，那么他必然不含奇数环。

染色法：

先随意取出一个未染色的点，然后对其染色，把其相邻的点染上其他颜色（二染色），如果所有点都染完也不存在冲突的话，那么就是二分图。

染色的过程就是遍历所有点的过程，所以深搜和宽搜都可以。

二染色技巧：1代表一种颜色,2代表一种颜色，每次用3减去当前颜色就是另一种颜色了。

注意：

1.二分图是无向图，一个边要在邻接矩阵中存储两次。

2.二分图不一定是联通的，分成多个二分集合也是可以的。

输入格式：
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。

输出格式：

如果给定图是二分图，则输出Yes，否则输出No。

深搜代码：

#include
#include
using namespace std;
 
const int N = 1e6 + 10;
int e[N], ne[N], h[N], idx = 0;
int color[N];
int n, m;
 
void add(int a, int b) {
    ne[idx] = h[a], e[idx] = b, h[a] = idx++;
}
 
bool dfs(int a, int b) {
    color[a] = b;
 
    for (int i = h[a]; i != -1; i = ne[i]) {
        if (!color[e[i]]) {
            if (!dfs(e[i], 3 - b))
                return false;
        }
 
         else if (color[e[i]] == b)return false;
    }
 
    return true;
}
 
int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    int a, b;
 
    while (m--) {
        cin >> a >> b;
        add(a, b), add(b, a);
    }
 
    bool flag = true;
    for (int i = 1; i <= n; i++) {
        if (!color[i]) {//如果没染色
            color[i] = 1;
            if (!dfs(i, 1)){flag = false;break;}
        }
    }
 
    if (flag)cout << "Yes";
    else cout << "No";
    return 0;
}