用C++写一篇二分图判定

二分图是指一个无向图可以分成两个互不相交的子集，使得同一子集内的节点没有边相连。判定一个无向图是否为二分图可以使用二分图判定算法，该算法基于染色法。

具体实现如下：

1. 选择一个起点，将其染成红色。
2. 将与起点相邻的所有节点染成蓝色。
3. 将与蓝色节点相邻的所有节点染成红色。
4. 重复步骤2和3，直到所有节点都被染色或发现某个节点已经被染成了两种颜色。
5. 如果染色完毕后没有发现任何一个节点被染成了两种颜色，那么该无向图是二分图，否则不是。

代码实现如下：

#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 50

int adj[MAX_VERTICES][MAX_VERTICES];
int color[MAX_VERTICES];

bool dfs(int v, int c, int n) {
    color[v] = c;
    for (int i = 0; i < n; i++) {
        if (adj[v][i]) {
            if (color[i] == c) {
                return false;
            }
            if (color[i] == 0 && !dfs(i, -c, n)) {
                return false;
            }
        }
    }
    return true;
}

bool isBipartite(int n) {
    for (int i = 0; i < n; i++) {
        if (color[i] == 0 && !dfs(i, 1, n)) {
            return false;
        }
    }
    return true;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u][v] = adj[v][u] = 1;
    }
    if (isBipartite(n)) {
        printf("The graph is bipartite.\n");
    } else {
        printf("The graph is not bipartite.\n");
    }
    return 0;
}

其中，dfs函数用于递归地进行染色操作，color数组用于记录节点的颜色，1表示红色，-1表示蓝色。isBipartite函数用于遍历所有节点，如果发现某个节点还没有被染色，就从该节点开始进行染色操作，如果染色过程中出现了相邻节点颜色相同的情况，就直接返回false，表示该无向图不是二分图。如果遍历完所有节点都没有出现相邻节点颜色相同的情况，就返回true，表示该无向图是二分图。

在主函数中，先读入无向图的节点数n和边数m，然后构建邻接矩阵。最后调用isBipartite函数进行判定，如果返回true，就输出该无向图是二分图，否则输出该无向图不是二分图。