二分图：

二分图又称作二部图，指的是图中的点可以分割成两个点集，每个点集中的点之间没有边将他们相连。一个图是二分图，那么他必然不含奇数环。

染色法：

先随意取出一个未染色的点，然后对其染色，把其相邻的点染上其他颜色（二染色），如果所有点都染完也不存在冲突的话，那么就是二分图。

染色的过程就是遍历所有点的过程，所以深搜和宽搜都可以。

二染色技巧：1代表一种颜色,2代表一种颜色，每次用3减去当前颜色就是另一种颜色了。

注意：

1.二分图是无向图，一个边要在邻接矩阵中存储两次。

2.二分图不一定是联通的，分成多个二分集合也是可以的。

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

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

输出格式：

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

深搜代码：

#include
#include
using namespace std;const int N = 1e6 + 10;
int e[N], ne[N], h[N], idx = 0;
int color[N];
int n, m;void add(int a, int b) {ne[idx] = h[a], e[idx] = b, h[a] = idx++;
}bool dfs(int a, int b) {color[a] = b;for (int i = h[a]; i != -1; i = ne[i]) {if (!color[e[i]]) {if (!dfs(e[i], 3 - b))return false;}else if (color[e[i]] == b)return false;}return true;
}int main() {memset(h, -1, sizeof h);cin >> n >> m;int a, b;while (m--) {cin >> a >> b;add(a, b), add(b, a);}bool flag = true;for (int i = 1; i <= n; i++) {if (!color[i]) {//如果没染色color[i] = 1;if (!dfs(i, 1)){flag = false;break;}}}if (flag)cout << "Yes";else cout << "No";return 0;
}