二分图的判别（染色法、匈牙利算法）

二分图的判别：
首先二分图是指一个图如果没有奇数环，则该图是二分图。
其实这两种算法都是基于dfs来做的，要深刻理解每个算法的dfs指代的是什么。
1、染色法：所谓的染色是指所有边的每一条边的两个端点颜色不同，算法思路就是让每个顶点都做一次dfs，判断其中有无同一条边的端点颜色相同。

#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 2020, INF = 0x3f3f3f;
int m, n;
int h[N], e[M], ne[M], idx; // 注意不是e[N]和ne[N]
int color[N];
int add(int a, int b)
{
   e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool dfs(int u, int c)
{
   color[u] = c;
   for (int i = h[u]; i != -1; i = ne[i])
   {
      int j = e[i];
      if (!color[j])
      {
         if (!dfs(j, 3 - c))
            return false;
      }
      else if (color[j] == c)
         return false;
   }
   return true;
}

int main()
{
   cin >> m >> n;
   memset(h,-1,sizeof h);
   while (m--)
   {
      int a, b;
      cin >> a >> b;
      add(a, b), add(b, a);
   }
   bool flag = true;
   for (int i = 1; i <= n; i++)
   {
      if (!color[i])
      {
         if (!dfs(i, 1))
         {
            flag = false;
            break;
         }
      }
   }
   if (!flag)
      cout << "No" << endl;
   else
      cout << "Yes" << endl;
   return 0;
}

2、匈牙利算法:就是两个集合之间最多能匹配多少

#include <bits/stdc++.h>
using namespace std;

const int N = 101, M = 10020;
int n1, n2, m, res;         // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];               // 每位女生配对的男生编号是谁
bool st[N];                 // 表示第二个集合中的每个点是否已经被遍历过

void add(int a, int b)
{
   e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool find(int u)
{
   for (int i = h[u]; i != -1; i = ne[i])
   {
      if (!st[j])
      {
         int j = e[i];
         if (match[j] == 0 || find(match[j]))
         {
            match[j] = x;
            return true;
         }
      }
   }
   return false;
}

int main()
{
   cin >> n1 >> n2 >> m;
   memset(h, -1, sizeof h);
   while (m--)
   {
      int a, b;
      cin >> a >> b;
      add(a, b);
   }
   // 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
   for (int i = 1; i <= n1; i++)
   {
      memset(st, flase, sizeof st);
      if (find(i))
         res++;
   }
   cout << res << endl;
   return 0;
}