C++写一篇二分图判断

二分图是指将一个图中的所有节点分成两部分，使得同一部分内的节点不相连，不同部分内的节点之间有边相连的图。判断一个图是否为二分图的方法有很多，其中较为常用的是基于染色的方法。

具体来说，我们可以从一个节点开始遍历整个图，并将其染成一种颜色，然后将与其相邻的节点染成另一种颜色。在遍历过程中，如果发现相邻的两个节点颜色相同，则说明该图不是二分图；反之，如果所有节点都能被染成两种颜色，则该图为二分图。

在代码实现上，我们可以使用深度优先搜索或广度优先搜索来遍历图，并使用一个颜色数组来记录每个节点的颜色。具体步骤如下：

1. 从任意一个节点开始遍历图，将其染成一种颜色（比如红色），并将其入队/入栈。
2. 对于队列/栈中的每个节点，遍历其所有相邻节点：
- 如果相邻节点未被染色，将其染成另一种颜色（比如蓝色），并将其入队/入栈。
- 如果相邻节点已被染成与当前节点相同的颜色，说明该图不是二分图，直接返回false。
3. 如果所有节点都能被染成两种颜色，那么该图为二分图，返回true。

下面是一个使用深度优先搜索判断二分图的示例代码：

#include <stdio.h>
#include <stdbool.h>

#define MAXN 1000

int n, m;
int head[MAXN], nxt[MAXN], to[MAXN], idx;
int color[MAXN]; // 0: 未染色，1: 红色，2: 蓝色

void add_edge(int u, int v) {
    to[idx] = v;
    nxt[idx] = head[u];
    head[u] = idx++;
}

bool dfs(int u, int c) {
    color[u] = c;
    for (int i = head[u]; i != -1; i = nxt[i]) {
        int v = to[i];
        if (color[v] == c) return false; // 相邻节点颜色相同，不是二分图
        if (color[v] == 0 && !dfs(v, 3 - c)) return false; // 染色并遍历相邻节点
    }
    return true;
}

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

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
    if (is_bipartite()) {
        printf("This is a bipartite graph.\n");
    } else {
        printf("This is not a bipartite graph.\n");
    }
    return 0;
}

在这个示例代码中，我们使用邻接表来存储图，并在遍历时同时遍历与每个节点相邻的所有节点。如果发现相邻节点颜色相同，则直接返回false，否则将其染成另一种颜色并递归遍历相邻节点。最后，如果所有节点都能被染成两种颜色，则返回true，否则返回false。

需要注意的是，该算法并不保证在所有情况下都能正确判断二分图，因此在实际应用中需要根据具体情况选择合适的算法来判断。