二分图

二分图 - 图1

染色法

二分图当且仅当图中不含奇数环。由于图中不含有奇数环，所以染色过程中一定没有矛盾。
860. 染色法判定二分图
给定吧一个n个点m条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行两个整数n和m。
接下来m行，每行包含两个整数u和v，表示u和v之间存在一条边。
输出格式
如果给定图是二分图，则输出Yes，否则输出No。
数据范围
二分图 - 图2
输入样例：

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

输出样例：

  1. Yes

代码

  1. #include <cstring>
  2. #include <iostream>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 100010, M = 200010;
  9. int n, m;
  10. int h[N], e[M], ne[M], idx;
  11. int color[N];
  13. void add(int a, int b) {
  14.     e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
  15. }
  17. bool dfs(int u, int c) {
  18.     color[u] = c;
  19.     for (int i = h[u]; i != -1; i = ne[i]) {
  20.         int j = e[i];
  21.         if (!color[j]) {
  22.             if (!dfs(j, 3 - c)) return false;
  23.         } else if (color[j] == c) return false;
  24.     }
  25.     return true;
  26. }
  28. int main() {
  29.     scanf("%d%d", &n, &m);
  30.     memset(h, -1, sizeof h);
  32.     while (m --) {
  33.         int a, b;
  34.         scanf("%d%d", &a, &b);
  35.         add(a, b), add(b, a); 
  36.     }
  37.     bool flag = true;
  38.     for (int i = 1; i <= n; i ++) 
  39.         if (!color[i]) {
  40.             if (!dfs(i, 1)) {
  41.                 flag = false;
  42.                 break;
  43.             }
  44.         }
  45.     if (flag) puts("Yes");
  46.     else puts("No");
  47.     return 0;
  48. }

匈牙利算法

861. 二分图的最大匹配
给定一个二分图，其中左半部分包含n1个点（编号1~n1），右半部分包含n2个点（编号1~n2）, 二分图包含m条边。数据保证任意一条边的两个端点都不可能在同一部分中。
求二分图的最大匹配数。
输入格式
第一行包含三个整数n1，n2和m.
接下来m行，每行包含两个整数u和v，表示左半部点集中的点u和右半部点集中的点v之间存在一条边。
输出格式
输出一个整数，表示二分图的最大匹配数。
数据范围
二分图 - 图3,
二分图 - 图4,
二分图 - 图5,
二分图 - 图6
输入样例

输出样例