二分图

• 0. 概述
• 1. 染色法
• 2. 匈牙利算法

0. 概述

• 二分图当且仅当图中不含奇数环，可以把所有点划分成两边，使得所有的边都是在集合之间的，集合内没有边。

​ 如果图中存在奇数环，那么会出现下面这种自相矛盾的情况。

1. 染色法

时间复杂度O(n+m)，用于判断一个图是否为二分图

只要图中不存在奇数环，染色过程就不会出现矛盾。

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

// 染色法:
// for v=1~n: 如果没有染色,dfs(v)
// 宽搜和深搜都能实现,但是深搜代码短
const int N=1e5+10;
const int M=(1e5+10)*2; // 无向图

int n,m;
int h[N],e[M],ne[M],idx;
int color[N];

void add(int a,int b) {
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool dfs(int u,int c) {
	color[u]=c; // 把当前点染成c色
	// 遍历与u相连的所有边
	for(int i=h[u];i!=-1;i=ne[i]) {
		// 取出相连的边的点
		int j=e[i];
		// 如果没有染色
		if(!color[j]) {
			// 3-c:如果c为1,则3-c为2,表示染成2色;如果c为2,则3-c为1,表示染成1色
			// 如果无法像这样染色,则返回false
			if(!dfs(j,3-c))
				return false;
		}
		// 如果颜色发生冲突,则直接返回false
		else if(color[j]==c)
			return false;
	}
	return true;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	memset(h,-1,sizeof h);
	while(m--) {
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	bool flag=true; // 未发生冲突
	for(int i=1;i<=n;i++) {
		// 如果没有染色
		if(!color[i]) {
			// 如果深搜发生冲突(染色冲突)
			if(!dfs(i,1)) {
				flag=false;
				break;
			}
		}
	}
	if(flag)
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
}
/*
4个点4条边
输入样例:
4 4
1 3
1 4
2 3
2 4
输出样例:
Yes
/*

2. 匈牙利算法

时间复杂度O(mn)，实际执行时间远小于O(mn)：求二分图的最大匹配数

• 注意需要满足是二分图这个前提才能使用匈牙利算法。

• 下面这个图个人感觉有问题，应该是先 (1,5)，后找到 (2,8)，再找到 (3,5) 这时发现5已经被1占有，所以1退而求其次找到7，变为 (1,7)，对于4，只有 (4,8)，但2也仅与 8 相连，所以最大匹配数为3，匹配为：(1,7)、(2,8)、(3,5)

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

// 没有两条边共用一个点,表示匹配
// 求图中的最大匹配数 

const int N=5e2+2;
const int M=1e5+10;

int n1,n2,m;
int h[N],e[M],ne[M],idx;
int match[N];
bool st[N];

void add(int a,int b) {
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool find(int x) {
	// 去查找这个与这个点相连的所有边的点集
	for(int i=h[x];i!=-1;i=ne[i]) {
		int j=e[i];
		if(!st[j]) {
			st[j]=true;
			// 如果这个点还没有和任何点匹配,并且也没有其他点与自身相连,则返回true
			if(match[j]==0 || find(match[j])) {
				match[j]=x;
				return true;
			}
		}
	}
	return false;
}

int main() {
	cin>>n1>>n2>>m;
	memset(h,-1,sizeof h);
	while(m--) {
		int a,b;
		cin>>a>>b;
		add(a,b); // 有向图
	}
	int res=0; // 存放最终答案
	// 遍历二分图中n1这个点集
	for(int i=1;i<=n1;i++) {
		memset(st,false,sizeof st); // 用于寻找增广路径时重置st
		// 如果能找到匹配点,则res++
		if(find(i))
			res++;
	}
	cout<<res<<endl;
	return 0;
}
/*
左边2点,右边2点,共4条边
1 1(表示左边点1和右边点1有边)
输入样例:
2 2 4
1 1
1 2
2 1
2 2
输出样例:
2
*/

打赏