如何用染色法判断二分图？

53.Acwing基础课第860题-简单-染色法判定二分图 题目描述 给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。 请你判断这个图是否是二分图。 输入格式 第一行包含两个整数 n 和 m。 接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。 输出格式 如果给定图是二分图，则输出 Yes，否则输出 No。 数据范围 1≤n,m≤105， 输入样例： 4 4 1 3 1 4 2 3 2 4 输出样例： Yes 代码： // 包含memset函数所需的头文件（用于初始化邻接表） #include <cstring> // 标准输入输出头文件（scanf/printf/puts依赖） #include <iostream> // 算法库（本代码未直接使用，属于通用模板保留） #include <algorithm> // 使用std命名空间，避免重复写std:: using namespace std; // 常量定义： // N：最大顶点数（题目通常约束1e5级别） // M：最大边数（无向图每条边需存两次，故设为2e5） const int N = 100010, M = 200010; // 全局变量： int n, m; // n：顶点数，m：边数 // 邻接表存储无向图： int h[N]; // h[u]：顶点u的邻接表表头（初始为-1，表示无邻边） int e[M]; // e[idx]：第idx条边的终点顶点 int ne[M]; // ne[idx]：第idx条边的下一条边的索引（链表结构） int idx; // 边的计数器（新增边时自增） int color[N]; // 染色数组：0=未染色，1/2=两种不同颜色（二分图的二染色） // 邻接表添加边的函数（无向图需双向添加） // a：边的起点，b：边的终点 void add(int a, int b) { e[idx] = b; // 记录第idx条边的终点是b ne[idx] = h[a]; // 让第idx条边指向a当前的表头（链表前驱） h[a] = idx ++ ; // 更新a的表头为当前边的索引，边计数器+1 } // DFS染色函数：给顶点u染颜色c，返回是否染色成功（无矛盾） // 核心逻辑：相邻顶点必须染相反颜色，若出现同色则说明存在奇环，不是二分图 bool dfs(int u, int c) { color[u] = c; // 给当前顶点u染颜色c（1或2） // 遍历顶点u的所有邻接顶点（邻接表遍历） // i = h[u]：从u的表头边开始，i=-1表示遍历结束 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; // j是u的邻接顶点（当前边的终点） if (!color[j]) // 若j未染色，递归给j染相反颜色 { // 3 - c：实现1和2的互转（c=1则3-1=2，c=2则3-2=1） // 若递归染色失败（返回false），则整体染色失败 if (!dfs(j, 3 - c)) return false; } // 若j已染色，且颜色和u相同→相邻顶点同色，染色矛盾（存在奇环） else if (color[j] == c) return false; } return true; // 顶点u的所有邻接顶点染色无矛盾，返回成功 } int main() { // 输入顶点数n和边数m（scanf效率更高，适配大数据量） scanf("%d%d", &n, &m); // 初始化邻接表表头：所有顶点的表头设为-1（表示初始无邻边） memset(h, -1, sizeof h); // 输入m条无向边，构建邻接表 while (m -- ) { int a, b; scanf("%d%d", &a, &b); // 无向图需双向加边：a→b 和 b→a add(a, b), add(b, a); } bool flag = true; // 标记是否是二分图（初始假设是） // 遍历所有顶点（处理多连通块：图可能有多个互不连通的部分） for (int i = 1; i <= n; i ++ ) if (!color[i]) // 若顶点i未染色（属于新的连通块） { // 从i开始DFS染色，初始染颜色1 // 若染色失败（返回false），说明存在奇环，不是二分图 if (!dfs(i, 1)) { flag = false; break; // 只要有一个连通块染色失败，直接终止遍历 } } // 根据flag输出结果：是二分图输出Yes，否则输出No if (flag) puts("Yes"); else puts("No"); return 0; }