二分图

二分图 当且仅当图中不含奇数环。
二分图就是将图中的点分成左右两个集合，每条边都在两个集合之间
染色法判断是不是二分图
思路：利用dfs将每个点进行染色，将某个点染成白色，则以这个点为中心的其他点染成黑色，用1表示白色，用2表示黑色，0表示没有染过色，可以建立一个数组color[]，来存储染色情况，每次dfs先判断是否染色，如果没有就染成和上一个点不一样的颜色，可以用3去减，表示相反的颜色，如果有则判断是不是和上一点的颜色一样，如果一样就是有矛盾，表示出现了奇数环，则返回false，否则返回true。（给dfs传入的参数有两个一个是点，一个是染的颜色，可以设置一个默认值，默认传1）数据结构用邻接表来存图。因为每个点可能不会都是连通的，所以要遍历每一个点，判断是否染色，如果染过则跳过，如果没有则进行一遍dfs。为了判断最后的结构，我们需要一个判断的表示，所以可以新建一个布尔变量，一开始设置为true，之后如果某一次dfs返回值为false则将其设置为false，然后跳出循环。当循环结束之后只要判断这个布尔变量是否为true，为true则说明染色过程很顺利，该图是二分图，否则就不是二分图。
例题：

染色法判定二分图

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

4 4
1 3
1 4
2 3
2 4

输出样例：

Yes

需要注意的是因为存的是无向图，所以边的数量应该是两倍于给的数量（相当于存两个方向相反的有向边）

匈牙利算法求二分图中最大的匹配数
思路：题目会给出一个二分图，先是遍历左边的点，每次遍历都遍历一遍那个点所连的边，让其和右边的点看能不能匹配，如果能那就匹配，如果不能就看一下那个被匹配的点于其匹配的那个点还有没有其他边的点可以与之匹配，如果可以，那就让那个点去匹配其他点，然后让现在这个点和被匹配的点匹配。去匹配其他点的过程是一个迭代的过程。数据结构是用的邻接表来存。对于手写邻接表中e[] , ne[] 的大小，应该是边的大小，因为每一个h都可以引出至多m（边数）条边，就是至多存有m个相连的点。定义一个bool st[]，表示被考虑过，每次遍历都要清空一下，表示在后面的迭代过程不会出现重复考虑的情况。定义一个int match[] , 用来存的是被匹配的点去匹配他的点。每次匹配成功就往答案中+1，当循环遍历完之后得到的就是最大匹配数。

例题：

二分图的最大匹配

给定一个二分图，其中左半部包含 n1 个点（编号1∼n1），右半部包含 n2 个点（编号 1∼n2），二分图共包含 m 条边。
数据保证任意一条边的两个端点都不可能在同一部分中。
请你求出二分图的最大匹配数。
二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
输入格式
第一行包含三个整数 n1、 n2和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。
输出格式
输出一个整数，表示二分图的最大匹配数。
数据范围 1≤n1 , n2≤500 , 1≤u≤n1 1≤v≤n2 , 1≤m≤1e5
输入样例：

2 2 4
1 1
1 2
2 1
2 2

输出样例：

2

思路：虽然没有说是有向图还是无向图，但是根据匈牙利算法的实现方式，可以当作单向图去存，且必须是去匹配的集合作为去指向的一方。

//find()函数
bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (!match[j] || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}