思路：

原理：一个图是二分图当且仅当图中不含奇数环，当且仅当染色法无矛盾！
dfs，将临点染成不同颜色，染色失败返回false
时间复杂度 O(n + m)

模板

860. 染色法判定二分图

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 u和 v，表示点 u 和点 v 之间存在一条边。
输出格式
如果给定图是二分图，则输出 Yes，否则输出 No。
数据范围
1≤n,m≤105
输入样例：

  1. 4 4
  2. 1 3
  3. 1 4
  4. 2 3
  5. 2 4

输出样例：

  1. Yes

代码：

  1. // dfs
  2. import java.util.*;
  4. public class Main {
  5.     static int n, m, idx;
  6.     static int[] h, e, ne, color;
  7.     public static void main(String[] args) {
  8.         Scanner sc = new Scanner(System.in);
  9.         n = sc.nextInt();
  10.         m = sc.nextInt();
  11.         h = new int[n + 1];
  12.         Arrays.fill(h, -1);
  13.         e = new int[2*m];
  14.         ne = new int[2*m];
  15.         color = new int[n + 1];
  17.         while (m-- > 0) {
  18.             int a, b;
  19.             a = sc.nextInt();
  20.             b = sc.nextInt();
  22.             add(a, b);
  23.             add(b, a);
  24.         }
  26.         boolean flag = true;
  27.         for (int i = 1; i <= n; i++) {
  28.             //第1个点还未被染色
  29.             if (color[i] == 0) {
  30.                 //尝试将其染成1
  31.                 if (!dfs(i, 1)) {
  32.                     flag = false;
  33.                     break;
  34.                 }
  35.             }
  36.         }
  37.         if (flag) System.out.println("Yes");
  38.         else System.out.println("No");
  39.     }
  41.     static boolean dfs(int u, int c) {
  42.         color[u] = c;
  44.         for (int i = h[u]; i != -1; i = ne[i]) {
  45.             //u当前临边为j
  46.             int j = e[i];
  48.             //如果j所在点为被染色，尝试将其染色
  49.             if (color[j] == 0) {
  50.                 if (!dfs(j, 3 - c)) return false;
  51.             }
  52.             //如果j所在点已经被染色，判断下是否与c相同
  53.             if (color[j] == c) return false;
  54.         }
  56.         return true;
  57.     }
  59.     static void add(int a, int b) {
  60.         e[idx] = b;
  61.         ne[idx] = h[a];
  62.         h[a] = idx ++;
  63.     }
  64. }
  1. //bfs
  2. import java.util.*;
  4. public class Main {
  5.     static int n, m, idx;
  6.     static int[] h, e, ne, color;
  7.     public static void main(String[] args) {
  8.         Scanner sc = new Scanner(System.in);
  9.         n = sc.nextInt();
  10.         m = sc.nextInt();
  11.         h = new int[n + 1];
  12.         Arrays.fill(h, -1);
  13.         e = new int[2*m];
  14.         ne = new int[2*m];
  15.         color = new int[n + 1];
  17.         while (m-- > 0) {
  18.             int a, b;
  19.             a = sc.nextInt();
  20.             b = sc.nextInt();
  22.             add(a, b);
  23.             add(b, a);
  24.         }
  26.         boolean flag = true;
  27.         for (int i = 1; i <= n; i++) {
  28.             //第1个点还未被染色
  29.             if (color[i] == 0) {
  30.                 //尝试将其染成1
  31.                 if (!bfs(i, 1)) {
  32.                     flag = false;
  33.                     break;
  34.                 }
  35.             }
  36.         }
  37.         if (flag) System.out.println("Yes");
  38.         else System.out.println("No");
  39.     }
  41.     static boolean bfs(int u, int c) {
  42.         color[u] = c;
  43.         Deque<Integer> q = new LinkedList<>();
  44.         q.offer(u);
  45.         while (!q.isEmpty()) {
  46.             int cur = q.poll();
  47.             c = 3 - color[cur];
  48.             for (int i = h[cur]; i != -1; i = ne[i]) {
  49.                 int j = e[i];
  50.                 if (color[j] == 0) {
  51.                     color[j] = c;
  52.                     q.offer(j);
  53.                 } else if (color[j] != c)
  54.                     return false;
  55.             }
  56.         }
  57.         return true;
  58.     }
  60.     static void add(int a, int b) {
  61.         e[idx] = b;
  62.         ne[idx] = h[a];
  63.         h[a] = idx ++;
  64.     }
  65. }
  1. //并查集
  2. import java.util.*;
  4. public class Main {
  5.     static int n, m, idx;
  6.     static int[] h, e, ne, color;
  7.     public static void main(String[] args) {
  8.         Scanner sc = new Scanner(System.in);
  9.         n = sc.nextInt();
  10.         m = sc.nextInt();
  11.         h = new int[n + 1];
  12.         Arrays.fill(h, -1);
  13.         e = new int[2*m];
  14.         ne = new int[2*m];
  15.         color = new int[n + 1];
  17.         while (m-- > 0) {
  18.             int a, b;
  19.             a = sc.nextInt();
  20.             b = sc.nextInt();
  22.             add(a, b);
  23.             add(b, a);
  24.         }
  26.         for (int i = 1; i <= n; i++)
  27.             color[i] = i;
  29.         boolean flag = true;
  30.         label: for (int i = 1; i <= n; i++) {
  31.             if (h[i] == -1) continue;   //当前点没有出边，孤立点直接跳过
  32.             int first = e[h[i]];
  33.             int c = find(color[i]);
  34.             for (int k = h[i]; k != -1; k = ne[k]) {
  35.                 int j = e[k];
  36.                 if (find(j) == c) {
  37.                     flag = false;
  38.                     break label;
  39.                 }
  40.                 color[find(j)] = find(first);
  41.             }
  42.         }
  43.         if (flag) System.out.println("Yes");
  44.         else System.out.println("No");
  45.     }
  47.     static int find(int x) {
  48.         return x == color[x] ? x : (color[x] = find(color[x]));
  49.     }
  51.     static void add(int a, int b) {
  52.         e[idx] = b;
  53.         ne[idx] = h[a];
  54.         h[a] = idx ++;
  55.     }
  56. }