染色法

染色法判定二分图的方法很好记，就和我们人工判定的做法差不多，勤勤恳恳地一个点一个点上色，直到发现不对劲为止。
具体做法是：遍历图，在扩展每个结点的时候，都把相邻结点染上和它相反的颜色。如果访问到了已经染上颜色的结点，则一定不再扩展该结点（否则会死循环），如果这个结点的颜色不对就报错。
用 DFS 或 BFS 都可以。DFS 代码如下。
BFS 实现思路：每次从队首取出一个结点u，看看从它能到达的所有结点v。如果v已经有颜色了，检查该颜色但不扩展结点v；如果v还没有颜色，给它上色并塞入队列，等待下次取出扩展。
算法的时间复杂度就是遍历一张图的时间复杂度，O(n+m)。

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
int n, m;
int h[M], e[M], ne[M], idx;
int clr[N];
void add(int u, int v) {
  e[idx] = v;
  ne[idx] = h[u];
  h[u] = idx ++ ;
}
bool dfs(int u, int color) {
  if (clr[u]) { // 遇到已经染色的结点，判断这个颜色对不对
    return clr[u] == color;
  }
  clr[u] = color;
  for (int i = h[u]; i != -1; i = ne[i]) {
    int v = e[i];
    if (!dfs(v, 3 - color)) {
      return false;
    }
  }
  return true;
}
int main() {
  cin >> n >> m;
  memset(h, -1, sizeof h);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    add(u, v);
    add(v, u);
  }
  bool flag = true;
  for (int i = 1; i <= n; i++) { // 遍历每个连通块
    if (!clr[i] && !dfs(i, 1)) {
      flag = false;
      break;
    }
  }
  cout << (flag ? "Yes\n" : "No\n");
  return 0;
}