【图论】——二分图
文章目录
定义
*若一张 N N N节点无向图可以分为 A , B A,B A,B两个交集为空的非空集合，并且同一集合内部的点之间没有连通边，则称该图为二分图
定理
- 一张二分图中，一定没有不存在点数为奇数的环（否则环内会有点属于两边集合，矛盾）
二分图判定
染色法
- 使用黑白两种颜色，如果一个点当前为白色，则它所有邻边都是黑色
- 因此，当二分图中某一点颜色确定，图中所有点的颜色就都确定了
- 若发生冲突，则说明存在点数为奇数的环
- 可以用一个dfs来实现染色，复杂度为 O ( n + m ) O(n+m) O(n+m)（点数加边数）
int n, m;//点数、边数
int e[N * 2], ne[N * 2], h[N], idx;//邻接表
int color[N];//存储每个点的颜色
void add(int a, int b)//邻接表存储
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
/*
颜色选择：
用1，和2代表两种颜色（黑白），切换颜色用3-当前颜色即可
*/
bool dfs(int x, int c)
{
color[x] = c;//将x染为c
for (int i = h[x]; i != -1; i = ne[i]) {//遍历x的所有邻边
int j = e[i];
if (!color[j]) {//如果没染色就进入下一层染色
if (!dfs(j, 3 - c))//3-c颜色切换，如果发生冲突返回false
return false;
} else if (color[j] == c)//如果染过色但是发生冲突，也是false
return false;
}
return true;//染色顺利，返回true
}
//调用染色法
bool flag = true;//用一个flag标记，初始化为true
for (int i = 0; i < n; i++) {
if (!color[i]) {
if (!dfs(i, 1)) {//如果返回了false证明出现冲突
flag = false;//flag改false，退出
break;
}
}
}
二分图最大匹配——匈牙利算法（增广路算法）
最大匹配
- 任意两条边都没有公共端点，则称为一组匹配，包含边数最多的匹配称为最大匹配
- 若为二分图中的最大匹配，当且仅当该图中不存在该匹配的增广路
- 简而言之，不能有两个点公用一条边，都是 A 1 A_1 A1对 B 1 B_1 B1的关系，类似于“一夫一妻”
算法思路
- 遍历A或B其中一个集合
- 如果当前点的邻边未被占用，则用这条边将两点相连
- 如果邻边全部被占用，去寻找他的邻边是否有其他可以未被匹配的点，如果有，则更还邻边的匹配点，让他的邻边空出，让当前点与其相连
代码实现
int e[M], ne[M], h[N], idx;//邻接表存储
bool st[N];//存储枚举的集合点是否匹配
int match[N];//存储匹配对象
int n1, n2, m;//A，B集合元素个数，边数
void add(int a, int b)//邻接表存储
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
bool dfs(int x)
{
for (int i = h[x]; i != -1; i = ne[i]) {//枚举x的所有邻边
int j = e[i];
if (st[j])//如果已经匹配就跳过
continue;
st[j] = true;
if (!match[j] || dfs(match[j])) {
//当前点为枚举，或被枚举但是可以换点匹配
match[j] = x;//j与x 匹配
return true;//匹配成功
}
}
return false;//如果遍历完没有true则该点没法匹配
}
for (int i = 1; i <= n1; i++) {
memset(st, false, sizeof st);//每次要把状态清空，每次枚举互不影响，仅有match数组会记录枚举点
//因为可能枚举到后面之前匹配过的点会换点匹配，如果不清空，为true无法进行
if (dfs(i))//如果匹配成功，总匹配个数+1
res++;
}