二分图笔记

什么是二分图？

二分图一般针对无向图问题

一张图中，如果能够把全部的点分到两个集合中，保证两个集合内部没有任何边 ，图中的边只存在于两个集合之间，即为二分图

判断二分图

1. 染色法

即用两种颜色对于这张图进行染色，相邻的结点颜色不同，如果没有矛盾，这张图即为二分图。

复杂度O（m+n）

bool dfs(int u,int c) {	//u为当前结点，c为要染的颜色 
	color[u]=c;				//染色
	for (int i=h[u];~i;i=ne[i]){	
		int j=e[i];			//对于这个点连接的所有的点
		if(color[j]) {		//已经被染过色了
			if(color[j]==c) return false;
			//判断，如果两点颜色一样，染色冲突
		}
		else if(!dfs(j,3-c)) return false;
		//否则dfs去染下一个结点，赋予的颜色肯定要跟 c 不一样
	}
	return true;
}

bool check() {
	memset(color,0,sizeof color);		//0 —— 未染色，1 —— 黑色，2 —— 白色
	for(int i=1;i<=n;i++)
		if(color[i]==0)					//一旦某个点没染过色，dfs去染色
			if(!dfs(i,1)) return false;	//如果传回false显然失败，此图不是二分图
	return true;
}

匈牙利算法（求出二分图的最大匹配数）：

满足 是二分图 这个前提，才能使用匈牙利算法

最大匹配数：

        两个集合分别选一个点，这两个点之间有边就确认一段关系，最多的关系数量就是这张二分图的最大匹配。
        即在男女的两个集合中，每一对男女，如果之间有边即可确定一条关系，并且只能一夫一妻，看最多能组成多少对夫妻。

复杂度O（nm）

例题：活动 - AcWing 二分图的最大匹配

#include<bits/stdc++.h>
using namespace std;
const int N=505,M=10010;
int n1,n2,m,match[N],vis[N];	//match保存右侧结点已匹配成功的左侧节点 
vector<int>e[N];
bool find(int x){
	for(int i=0;i<e[x].size();i++){
		int t=e[x][i];
		if(!vis[t]){
			vis[t]=1;
			if(match[t]==0||find(match[t])){	//vis防止当match[t]非负时死循环 
				match[t]=x;
				return true;
			}
		}
	}
	return false;
}
int main(){
	scanf("%d%d%d",&n1,&n2,&m);
	for(int i=0;i<m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		e[a].push_back(b);			//由于只会从左侧查找右侧结点，所以只存单侧边即可 
	}
	int res=0;
	for(int i=1;i<=n1;i++){
		memset(vis,0,sizeof vis);	//每次重置vis数组 
		if(find(i)) res++;			//查找到结果res+1 
	}
	cout<<res;
	return 0;
}

最小点覆盖：

对于图中的每一条边，都至少有一个顶点在集合中，这个集合即为最小点覆盖。

特别的，在二分图中，最小点覆盖 = 最大匹配数

最大独立集：

最大独立集，指在一个图中选取最多多少个点，可以使得这些点所组成的集合内部任意两点间没有边

最大独立集 ==（总点数 - 最小点覆盖）

最小路径点覆盖：

用最少的点，覆盖图中全部的不相交路径的路径数
等于总点数 - 最小点覆盖 / 最大匹配数