常用算法代码模板 (3)：搜索与图论 - 6 个二分图

定义：二分图可将图中顶点划分两个集合，使得集合内顶点互不邻接，不同集合顶点可邻接

定理：图为二分图 $\iff$ 图中不含奇数环

6.1 染色法

时间复杂度：$O(n+m)$

判断是否是二分图

思想：若为二分图，则与黑点相连的点均为白色，与白点相连的点均为黑色（邻接顶点不得同色）

int n;			// V: [1 ... n]
int h[N], e[M], ne[M], idx;	// 邻接表图
int color[N];	// 每个点的颜色：-1未染色，0白色，1黑色

/* 用dfs给结点u染颜色c，一切顺利返回true，出现冲突则返回false */
bool dfs(int u, int c) {
    color[u] = c;	// 给结点u染颜色c
  
    for (int i = h[u]; ~i; i = ne[i]) {	// 遍历所有从结点u指出的点
        int v = e[i];
        if (color[v] == -1) {	// 若v未染色则将其染与u相反的色(!c)并判定是否冲突
            if (!dfs(v, !c)) return false;
        } else if (color[v] == c) return false;	// 若v与u同色则出现冲突
    }
  
    return true;
}

/* 用染色法判断图是否是二分图 */
memset(color, -1, sizeof color);
bool success = true;
for (int i = 1; i <= n; i++)	// 遍历所有顶点，若未染色则染白色并判定是否冲突
    if (color[i] == -1)
        if (!dfs(i, 0)) {
            success = false;
            break;
        }

6.2 匈牙利算法

时间复杂度：最差 $O(nm)$ ，实际运行时间一般远小于 $O(nm)$

用于求二分图的最大匹配数（匹配：某两个点有且只有他们之间有边，与别人无边）

匈牙利算法中只会用到从第1个集合指向第2个集合的边，所以这里只用存一个方向的边。

先欣赏y神讲解再看代码

int n1, n2;		// 二分图中两个集合的点数。集合1: [1 ... n1]、集合2: [1 ... n2]
int h[N], e[M], ne[M], idx;	// 邻接表图，只存集合1到集合2的边
int match[N];	// match[i] = j表示集合2的点i当前匹配集合1的点j（j=0表示暂无匹配）
bool st[N];		// st[i]标记集合2的点i是否已经被遍历过

/* 寻找与集合1的点u匹配集合2的点，返回是否成功 */
bool find(int u) {
    for (int i = h[u]; ~i; i = ne[i]) {	// "遍历所有可能的她"
        int v = e[i];
        if (!st[v]) {
            st[v] = true;
            if (match[v] == 0 || find(match[v])) {	// 判定"若她有则'去找他'"
                match[v] = u;	// 与她匹配
                return true;
            }
        }
    }
  
    return false;
}

/* 求最大匹配数 */
int res = 0;
for (int i = 1; i <= n1; i++) {	// 依次枚举集合1的每个点去匹配集合2的点
    memset(st, false, sizeof st);	// 每次重置遍历标记
    if (find(i)) res++;
}