二分图 二分图最大匹配

首先来说一下什么是二分图。

二分图

二分图又称作二部图，是图论中的一种特殊模型。
设G=(V, E)是一个无向图。如果顶点集V可分割为两个互不相交的子集X和Y，并且图中每条边连接的两个顶点一个在X中，另一个在Y中，则称图G为二分图。

性质

当且仅当无向图G的每一个环的结数均为偶数时，G才是二分图。如果无环，相当于每个环的结点数为0，故也视为二分图。

判断是否是二分图

这里我们用到染色法，用两种颜色来染这个图。如果该节点的颜色是0，那么所有与其相邻的节点的颜色都是1。最后判断是否满足上述条件即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010,M=2*N;
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 x,int c) //判断x点染c颜色对不对。
{
    color[x]=c; //给x染c色。 c=1,2
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!color[j]) //如果j点未被染色，判断它染另一种颜色是否合适。
        {
           if(!dfs(j,3-c)) return false; //c=1时候，另一种颜色为3-1=2
        }
           
        else if(color[j]==c) return false; //如果j点与x点颜色相同返回false
    }
    return true;
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        add(x,y),add(y,x);
    }
    bool flag=true;
    for(int i=1;i<=n;i++) //从1点开始，将未被染色的点染上1颜色。
    {
        if(!color[i])
        {
            if(!dfs(i,1))
            {
                flag=false;
                break;
            }
        }
    }
    if(flag) puts("Yes");
    else puts("No");
    return 0;
}
 

二分图最大匹配

首先什么是匹配： 给定一个二分图G，在G的一个子图M中， M的边集{E}中的任意两条
边都不交汇于同一个结点，则称M是一个匹配。

然后如何求出最大匹配？这里有一个很经典的算法：匈牙利算法。

算法流程：

1.从任意一个没有被配对的点x开始，从点x的边中任意选一条边。如果此时点i没有被配对那么配对成功，则找到了一条增广路。如果点i此时已经被配对了，那么可以尝试将点i与其他点配对。如果尝试成功，则找到一条增广路。这里用match[ ]来记录配对关系， 即match[i] = x。 并且将配对数+1。 这个过程我们用dfs来实现。

2.如果配对失败，就从点x的边中重选一条边尝试。直到点x配对成功或尝试完x所有的边。

3.接下来对没有配对的点一一进行配对，直到所有的点都尝试完毕找不到新的增广路。

#include<bits/stdc++.h>
#define re register int
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48) ; ch=getchar();}
	return x*f;
}
int n,m,tot;
const int M = 5e4+10;
int head[M],vis[M],match[M];
int cnt,ans;
struct edge{
	int to,nxt;
}e[M];
void add(int u,int v){
	e[++cnt].to = v;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}
bool find(int x){
	for(re i(head[x]) ; i ; i=e[i].nxt){
		int v=e[i].to;
		if(!vis[v]){ //如果这个点没有被访问过
			vis[v] = 1;
			if(!match[v]||find(match[v])){ //如果这个点没有匹配，
                                           //或者这个点匹配的点可以去匹配另一个点
				match[v]=x; //就把这个点跟x匹配
				return 1;
			}
		}
	}
	return 0;
}
signed main(){
	n=read(),m=read(),tot=read();
	for(re i(1) ; i<=tot ; ++i){
		int u,v;
		u=read(),v=read();
		add(u,v);
	}
	for(re i(1) ; i<=n ; ++i){
		memset(vis,0,sizeof(vis));
		if(find(i)) ans++; //记录最大匹配数
	}
	printf("%d",ans);
	return 0;
}