一.什么是二分图？：

引用了这个大佬的话：https://www.acwing.com/solution/content/105874/

              有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中，每个顶点集中没有边直接相连接！

              说人话的定义：图中点通过移动能分成左右两部分，左侧的点只和右侧的点相连，右侧的点只和左侧的点相连。

             下图就是个二分图：

                如果判断一个图是不是二分图？

                开始对任意一未染色的顶点染色。

                判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色。

                若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断。

                bfs和dfs可以搞定！

具体例子：

 1 给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。
 2 
 3 请你判断这个图是否是二分图。
 4 
 5 输入格式
 6 第一行包含两个整数 n 和 m。
 7 
 8 接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。
 9 
10 输出格式
11 如果给定图是二分图，则输出 Yes，否则输出 No。
12 
13 数据范围
14 1≤n,m≤10^5 
16 输入样例：
17 4 4
18 1 3
19 1 4
20 2 3
21 2 4
22 输出样例：
23 Yes

 1 #include 
 2 #include 
 3 #include 
 4 using namespace std;
 5 const int N = 1e5 + 10, M = 2 * 1e5 + 10;
 6 int e[M], ne[M], h[N], idx = 0; //链表保存;
 7 /* int st[N] */                 //其实不用st[N]，因为color[N]可以计入;
 8 int color[N];
 9 void add(int a, int b)
10 {
11     e[idx] = b, ne[idx] = h[a], h[a] = idx++;
12 }
13 bool dfs(int x, int num) // dfs的作用是将x点染色,并把它能到达的点染成不同颜色；
14 {//x代表正在看的点，num表示要染成的颜色：
15     color[x] = num;
16     for (int i = h[x]; i != -1; i = ne[i])
17     {
18         int j = e[i];
19         if (!color[j])
20         {
21             if (!dfs(j, 3 - num))//当前这个点染成1，那邻接的点染成2,正好可以用3-1表示，3-2同理：
22                 return false;
23         }
24         else if (color[j] == num) //这说明有相邻的点的颜色相同，即不是二分图
25             return false;
26     }
27     return true;
28 }
29 int main()
30 {
31     memset(h, -1, sizeof(h));
32     int n, m;
33     scanf("%d%d", &n, &m);
34     while (m--)
35     {
36         int a, b;
37         scanf("%d%d", &a, &b);
38         add(a, b), add(b, a);//因为是无向图，所以要保存一下两边
39     }
40     bool flag = true;
41     for (int i = 1; i <= n; i++)
42     {
43         if (!color[i])//即当这个点没有看过
44         {
45             if (!dfs(i, 1))
46             {
47                 flag = false;
48                 break;
49             }
50         }
51     }
52     if (flag)
53         printf("Yes\n");
54     else
55         printf("No\n");
56     return 0;
57 }

二. 二分图的应用--匈牙利算法

   二分图的最大匹配：

接下来我将用y总的“找妹子”的思想表达一下算法的想法:

 如图，我将两个点集分别设为 男，女，他们之间有如上的关系（用线连起来了），用线连起来的男女表示相互之间有好感，

现在我的任务是月老，要最大的使男女之间形成恋爱关系，（当然一定是一男一女才是配对了，不能一对多或多对一）如何作呢？：

以这个图为例：我们只看男生：

第一个男生 (一)他的第一个在意的女生是（2），且这个女生没有与其他男生建立关系，那么我就将他们匹配。

第一个男生匹配完成，接下来看下一个男生（二）,他在意的第一个女生是（1），这个女生也没有与其他男生建立关系，匹配；

第三个男生（三），发现他喜欢的第一个女生（2）以及匹配了，关键来了:

这个时候，男生（三）不会善罢甘休，他会找到与女生（2）匹配的男生（一）商谈一下，看一下男生（一）能否与其他女生去匹配，把女生（2）让给男生（三）。

巧了，男生（一）正好可以与另一个女生（4）匹配，那么这时男生（三）就可以与女生（2）在一起了。

然后男生（四）与女生（3）在一起。

匹配结束，最大匹配为4；

下面给出具体例子：

 1 给定一个二分图，其中左半部包含 n1 个点（编号 1～n1），右半部包含 n2 个点（编号 1～n2），二分图共包含 m 条边。
 2 
 3 数据保证任意一条边的两个端点都不可能在同一部分中。
 4 
 5 请你求出二分图的最大匹配数。
 6 
 7 二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。
 8 
 9 二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
10 
11 输入格式
12 第一行包含三个整数 n1、 n2 和 m。
13 
14 接下来 m 行，每行包含两个整数 u 和 v，表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。
15 
16 输出格式
17 输出一个整数，表示二分图的最大匹配数。
18 
19 数据范围
20 1≤n1,n2≤500,
21 1≤u≤n1,
22 1≤v≤n2,
23 1≤m≤105
24 输入样例：
25 2 2 4
26 1 1
27 1 2
28 2 1
29 2 2
30 输出样例：
31 2

 1 #include 
 2 #include 
 3 #include 
 4 using namespace std;
 5 const int N = 500 + 10, M = 1e5 + 10;
 6 int e[M], ne[M], h[N], idx = 0;
 7 int match[N]; //表示女生i,与男生match[i]匹配；
 8 bool st[N];   //在一次男生找女生的过程中记录一下这个女生是否以及被找过;
 9 void add(int a, int b)
10 {
11     e[idx] = b, ne[idx] = h[a], h[a] = idx++;
12 }
13 bool find(int x)
14 {
15     for (int i = h[x]; i != -1; i = ne[i])
16     {
17         int j = e[i];
18         if (!st[j])
19         {
20             st[j]=true;
21             if (match[j] == 0 || find(match[j]))//这里如果match[j]!=0说明这个女生有男生了
               //find(match[j])是为了看一下，match[j]这个男生能否找其他女生,用st[j]记录一下找过女生j了，当match[j]再找时不能找这个女生了
22             {
23                 match[j] = x;
24                 return true;
25             }
26         }
27     }
28     return false;
29 }
30 int main()
31 {
32     int n1, n2, m;
33     scanf("%d%d%d", &n1, &n2, &m);
34     memset(h,-1,sizeof(h));
35     while (m--)
36     {
37         int a, b;
38         scanf("%d%d", &a, &b);
39         add(a, b); //只要记录一下男生到女生的关系就可以;
40     }
41     int ans = 0;
42     for (int i = 1; i <= n1; i++)
43     {
44         memset(st, false, sizeof(st));//必须每一次都初始化为false,这个妹子有男朋友，并不影响当前这个男生去尝试
45         if (find(i))
46             ans++;
47     }
48     printf("%d", ans);
49     return 0;
50 }

对st[N]的理解有一位网友的：https://www.acwing.com/user/myspace/index/49357/

disheng  
对于st数组的理解：1.必须要存在，不存在就会出现find无限递归同一个女孩；2.必须每次要全部更新为false，否则男孩无法挖墙脚，从而会得不到最大匹配 (欢迎纠正)