关于二分图

二分图判定：不存在奇环。

深搜

class Solution {
public:
    vector<int> c;
    vector<vector<int>> g;
    bool isBipartite(vector<vector<int>>& graph) {
        g=graph;
        int n=g.size();
        c.resize(n);
        for(int i=0;i<n;i++){
            if(c[i]==0){
                if(!dfs(i,1))return false;
            }
        }
        return true;
         
    }
    bool dfs(int x,int co)
    {
        c[x]=co;
        for(int i=0;i<g[x].size();i++){
            int y=g[x][i];
            if(c[y]==0){
                 if(!dfs(y,-1*co))return false;
            }else if(c[y]==co){
                return false;
            }
        }
        return true;
    }
};

二分图最大匹配：

匹配：任意两条边都没有公共端点。

含边数最多的一组匹配称为最大匹配。

增广路：连接两个非匹配点，匹配边与非匹配边交替出现的路径。

增广路性质：

1.长度len为奇数

证明：因起点终点都为未匹配点，所以第一条边与最后一条边都是未匹配边，由于匹配边与非匹配边交替出现，所以路径长一定为奇数，非匹配边比匹配边多1.

2.路径上第1，3，5，…，len为非匹配边，2，4，…，len-1为匹配边

将所有边状态取反，原来的匹配边变为非匹配边，非匹配边变为匹配边，匹配边数+1.

最大匹配：当且仅当不存在增广路。

匈牙利算法：（增广路算法）

1.设S=Φ，即所有边都是非匹配边。

2.寻找增广路P,把路径上所有边状态取反，得到一个更大的匹配

3.重复步骤2，直至不存在增广路

如何找增广路？

依次给每个左部节点x找一个匹配的右部节点y，右部节点能与左部点匹配需满足下列条件之一：

1.y本身就是非匹配点

此时无向边（x,y)本身就是非匹配边，自己构成一条长度为1的增广路。

2.y已经与左部点x'匹配，但从x'出发能找到另一右部点y'与之匹配。

x~y~x'~y‘为一条增广路。

深搜，递归从x点找增广路，若找到，回溯时将路径状态取反。

一个节点由非匹配点变为匹配点后，绝不会变为非匹配点。

step1:对于一个没有匹配的顶点u，遍历其每条边，如果这条边上的另一个顶点v还未被匹配，则说明已经找到了一个匹配，匹配数++

step2:若v已经被匹配，则寻找v的匹配点w，再遍历其边，试图找到一个未匹配顶点。

step3：反复执行1、2，若找不到增广路了，退出。

POJ 1247

下附一个邻接表代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int N,M;
int ver[205*205];
int head[405];
int nxt[205*205];
int tot=1;
bool vis[405];
int match[405];
void add(int x,int y)
{
    ver[++tot]=y;
    //edge[tot]=0;
    nxt[tot]=head[x];
    head[x]=tot;
}
bool dfs(int x)
{
    int y;
    for(int i=head[x];i;i=nxt[i]){
        y=ver[i];
        if(!vis[y]){
            vis[y]=1;
            if(!match[y]||dfs(match[y])){
                match[y]=x;return true;
            }
        }
    }
    return false;
}
void init()
{
    memset(ver,0,sizeof ver);
    memset(head,0,sizeof head);
    memset(nxt,0,sizeof nxt);
    memset(match,0,sizeof match);
}
int main()
{
    int m,t,ans;
    while(scanf("%d%d",&N,&M)!=EOF)
    {
        init();

        ans=0;
        for(int i=1; i<=N; i++)
        {
            scanf("%d",&m);
            for(int j=0; j<m; j++)
            {
                scanf("%d",&t);
                add(i,t+N);
                add(t+N,i);
            }
        }
        for(int i=1;i<=N;i++){
            memset(vis,0,sizeof vis);
            if(dfs(i))ans++;
        }
        cout<<ans<<'\n';
    }
}

关于二分图

推荐阅读