二分图

什么是二分图
通俗的说就是将一个图能刚好分成两份就是二分图
感觉这里也需要用dfs来不断替换点

完全二分图

集合x和集合y每对顶点之间有且仅有一条边的图成为完全二分图

二分图判别方法

1.染色法
就是一条边对应的两个点必须是两种不同的颜色，并且整张图只可以有两种颜色

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
std::vector<int> g[N];
int c[N];

bool dfs(int x){
	for(auto y:g[x]){
		if(!c[y]){
			c[y]=3-c[x];
			if(!dfs(y)){
				return false;
			}
		}
		else{
			if(c[y]==c[x]){
				return false;
			}
		}
	}
	return true;
}

bool check(){
	memset(c,0,sizeof c);
	for(int i=1;i<=n;i++){
		if(!c[i]){
			c[i]=1;
			if(!dfs(i)){
				return false;
			}
		}
	}
	return true;

}
void solve(){
	//首先是建图,以无向图为例
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	if(check()){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
}

int main(){
	int t=1;
	while(t--){
		solve();
	}
	return 0;
}

二分图匹配

什么是二分图匹配问题？
就是将两个集合一个一个匹配，但是有可能一个集合的点对应另一个集合多个点，我们需要做的就是找到合适的边，使得完成最大匹配
完备匹配：二分图G中的最大匹配包含的边数=V1，无论再怎么加边都没办法再多，这就是完备匹配
交错路径
增广路径

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int n1,n2;
int v[N];
std::vector<int> g[N];
bool b[N];
bool find(int x){
	b[x]=true;
	for(auto y:g[x]){
		if(!v[y]||(!b[v[y]]&&find(v[y]))){
			v[y]=x;
			return true;
		}
	}
	return false;
	
}
int match(){
	int ans=0;
	memset(v,0,sizeof v);
	for(int i=1;i<=n1;i++){
		memset(b,false,sizeof b);
		if(find(i)){
			++ans;
		}
	}
	return ans;
}

void solve(){
	cin>>n>>m;
}
int main(){
	int t=1;
	while(t--){
		solve();
	}
	return 0;
}

棋盘覆盖问题

比如在n * n的棋盘上放置多米诺骨牌，其中m个各自已经放置了棋子，这些点不可以被覆盖，请你求出最多的放置骨牌的个数，也可以理解为骨牌最多可以覆盖多少个格子
思路：
先对空地方的棋盘进行染色，将图变成一个二分图，然后将其划分，最后求最大匹配就可以了
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;

int n,m;
int a[50][50];
int n1,n2;
int r[50][50];
int v[820];
bool b[820];
int D[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
std::vector<int> g[N];
bool find(int x){
	b[x]=true;
	for(auto y:g[x]){
		if(!v[y]||(!b[v[y]]&&find(v[y]))){
			v[y]=x;
			return true;
		}
	}
	return false;

}
int match(){
	int ans=0;
	memset(v,0,sizeof v);
	for(int i=1;i<=n1;i++){
		memset(b,false,sizeof b);
		if(find(i)){
			++ans;
		}
	}
}
void solve(){
	cin>>n>>m;
	memset(a,0,sizeof a);
	n1=n2=0;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		a[x][y]=1;//表示已经被占用了
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(!a[i][j]){
				if((i+j)&1){//判断行列之后是奇数还是偶数
					r[i][j]=++n2;
				}
				else{
					r[i][j]=++n1;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(!a[i][j]&&!((i+j)&1)){
				for(int k=0;k<4;k++){
					int x=i+D[k][0];
					int y=j+D[k][1];
					if(x<1||x>n||y<1||y>n||a[x][y]){
						continue;
					}
					g[r[i][j]].push_back(r[x][y]);
				}
			}
		}
	}
	cout<<2*match()<<endl;//放置了多少个牌就占了2倍的格子
	return ;


} 
int main(){
	int t=1;
	while(t--){
		solve();
	}
	return 0;

}