算法学习笔记（二分图染色）

本文主要是介绍算法学习笔记（二分图染色），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

首先我们需要明确什么是二分图：如果无向图 $G = (V, E)$ 的所有点可以分为两个集合 $V_1、V_2$ ，所有的边都在 $V_1$ 和 $V_2$ 之间，而 $V_1$ 或 $V_2$ 的内部没有边，称 $G$ 是一个二分图。

直接说结论：如果一个图是二分图，那么它一定没有边数量为奇数的环。

判断一个图是否为二分图，一般用“染色法”进行判断。

用两种颜色对所有点进行染色，要求处在一条边上的两个点的颜色不能相同，染色结束后，如果没有相邻点颜色相同，那就是二分图。

例题；【模板】二分图判定

题目描述

给定一个 $n$ 点 $m$ 边的无向图，请判定它是否是一个二分图。

如果是，输出 $" Y ES "$ ，反之输出 $" NO "$ 。

输入描述

第一行三个整数 $n$ , $m$ 。 $\leq n,m \leq 2 \times 10^5)$

接下来 $m$ 行，每行两个整数 $x, y$ 表示一条无向边。 $\leq x,y \leq n,x \not = y)$

输出描述

一行输出结果。

输入样例1

输出样例1

NO

输入样例2

输出样例2

YES

染色法使用 $df s$ 实现，下边给出带注释代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;int n, m;
vector<int> g[N];
int col[N];     //存储颜色，-1表示未染色，0、1表示颜色bool dfs(int x) //染色
{for(const auto &y : g[x])       //遍历所有边{if(col[y] == -1)            //如果没被染色{col[y] = col[x] ^ 1;    //染上不同颜色//下一个节点染不上色就返回flase，将flase传到main函数if(!dfs(y)) return false;}else if(col[y] == col[x]) return false;     //如果已经被染色但是和该节点颜色相同，也返回false}return true;
}void solve()
{cin >> n >> m;//存图for(int i = 1; i <= m; ++i){int x, y; cin >> x >> y;g[x].push_back(y);g[y].push_back(x);}//初始化for(int i = 1; i <= n; ++i) col[i] = -1;int ans = 1;for(int i = 1; i <= n; ++i){if(col[i] == -1){//用与运算只要有一个没染色答案就变成0ans &= dfs(i); }}cout << (ans ? "YES" : "NO") << '\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ = 1;while(_--) solve();return 0;
}