染色法判定二分图——图论（C++）

一、基本定义与思想

1、二分图

二分图又称作二部图，是图论中的一种特殊模型。 设G=(V, E)是一个无向图。如果顶点集 V可分割为两个互不相交的子集X和Y，并且图中每条边连接的两个顶点一个在 X中，另一个在 Y中，则称图G为二分图。

如果没有环，就一定可以分成二分图 如果存在偶数环，也可分成二分图 如果存在奇数环，就不能分成二分图（有矛盾）

2、性质

定理：当且仅当无向图G的每一个环 的结点数均是偶数时，图G才是一个二分图。如果无环，相当于每的结点数为 0，故也视为二分图。

3、判定

如果一个图是连通的，可以用如下的染色法判定是否二分图： 1、我们把X部的结点颜色设为0，Y部的颜色设为1。 2、从某个未染色的结点u开始，做BFS或者DFS 。 3、把u染为0，枚举u的儿子v。如果v未染色，就染为与u相反的颜色，如果已染色，则判断u与v的颜色是否相同，相同则不是二分图。 4、如果一个图不连通，则在每个连通块中作判定。

二、基本模板

时间复杂度是 O(n+m)O(n+m), nn 表示点数，mm 表示边数

int n; // n表示点数 int h[N], e[M], ne[M], idx; // 邻接表存储图 int color[N]; // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色 // 参数：u表示当前节点，c表示当前点的颜色 bool dfs(int u, int c) { color[u] = c; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (color[j] == -1) { if (!dfs(j, !c)) return false; } else if (color[j] == c) return false; } return true; } bool check() { memset(color, -1, sizeof color); bool flag = true; for (int i = 1; i <= n; i ++ ) if (color[i] == -1) if (!dfs(i, 0)) { flag = false; break; } return flag; } 作者：yxc 链接：https://www.acwing.com/blog/content/405/ 来源：AcWing

三、经典例题

AcWing 860. 染色法判定二分图 给定一个n个点m条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

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

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

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

数据范围 1≤n,m≤10⁵ 输入样例：

4 4 1 3 1 4 2 3 2 4

输出样例：

Yes #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 100010, M = 200010;// 无向图, 所以最大边数是2倍 int n, m; int h[N], e[M], ne[M], idx; int color[N]; //邻接表方式存储图, 无向图可能会连接M条边 //color[N], 为0代表还未染色省去一个bool数组,1代表染颜色1,2代表染颜色2 void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; }//返回是否可以成功将u染色为c bool dfs(int u, int c) { color[u] = c; //修改当前颜色 for (int i = h[u]; i != -1; i = ne[i])//尝试染链接边的颜色 { int j = e[i]; if (!color[j])//如果color[j]没有染过色 { if (!dfs(j, 3 - c)) return false;//如果不可以将j成功染色 } else if (color[j] == c) return false;//如果染过颜色且和c相同 } return true; } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while (m -- ) { int a, b; scanf("%d%d", &a, &b); add(a, b), add(b, a);// 无向图 } bool flag = true; for (int i = 1; i <= n; i ++ ) if (!color[i]) //如果未染色 { if (!dfs(i, 1)) { flag = false; break; //如果dfs返回false 说明出现矛盾 } } if (flag) puts("Yes"); else puts("No"); return 0; }