文章目录
前言
一、二分图
二、AcWing 860. 染色法判定二分图
本题分析
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：染色法判定二分图，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、二分图
二分图当且仅当图中不含奇数环
染色方法如图所示：
我们在遍历图的过程中，需要用BFS或是DFS去遍历，在本文的AC代码中，展示的是用DFS去遍历，下图来自ACWing算法基础课
二、AcWing 860. 染色法判定二分图
本题链接：AcWing 860. 染色法判定二分图
本博客给出本题截图：
本题分析
因为是无向图，所以进行add操作的时候需要add(u, v), add(v, u);，如何模拟染色：介绍一下这次的dfs过程，dfs函数中传了两个值，一个是点，另一个是颜色，我们在dfs的for循环中每次取得一个点，然后看这个点有没有被赋予颜色，如果没有被赋予颜色的话，我们就进行dfs(j, 3 - c);，因为我们的颜色只有1和2（当然你可以是2或7，或者其他的颜色，这里为了方便我们把一种颜色称为1，另一种颜色称为2），因为我们的dfs给点赋颜色的时候是1和2两种颜色交替的赋值的，所以在这里，我们只需要用一行代码dfs(j, 3 - c)就可以实现交叉赋颜色；如果下一个点有颜色了，且这个颜色和这个点的上一个点的颜色如果是一样的话即else if (color[j] == c)，那么显然是不合法的，返回false
AC代码
#include <cstdio> #include <cstring> using namespace std; const int N = 100010, M = 200010; int h[N], e[M], ne[M], idx; int color[N]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++; } 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]) { if (!dfs(j, 3 - c)) return false; } else if (color[j] == c) return false; } return true; } int main() { int n, m; scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while (m -- ) { int u, v; scanf("%d%d", &u, &v); add(u, v), add(v, u); } bool flag = true; for (int i = 1; i <= n; i ++ ) if (!color[i]) if (!dfs(i, 1)) { flag = false; break; } if (flag) puts("Yes"); else puts("No"); return 0; }
三、时间复杂度
关于染色法判定二分图的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
