主要是染色法和匈牙利法,都不错幺。
第一种可以理解为dfs,第二种类似最大流为问题,但是其实不难。

二分图???

我是这么理解的,一个图可以把他们的点分成两部分,同一部分的点之间互相不直接连接构成的图。
可以按照以下图理解。
graph_1
graph_2
从上面的图不难看出,这里面一定不能存在奇数环是吧!

染色法🎈

染色法很明确,就是染色,把点染成1或0,如果相邻点染色相同直接返回不是false。
这个过程就是简单的dfs,还是那种不用还原的。。

算法思路

  1. 初始化所有点的染色为**-1**。
  2. 选取一个点染色,将他的子节点染色成**!他的染色**。如果中间出现父亲染色=儿子染色直接返回false
  3. 重复2过程

staining_method_code🎉

bool dfs(int u,int c){
    memset(color,-1,sizeof clolor);
    color[u]=c;
    for(int i = h[i];i!=-1;i=ne[i]){
        int j = e[i];
        if(color[j]==-1){
            if(color(j,!c))return false;
        }
        else if(color[j]==c)return false;
    }
    return true;
}

匈牙利法求最大匹配

为什么叫这个名字我也不清楚。。。。
这个算法就是求一个二分图的最大匹配数目,其中保证给出的数据是二分图。

算法思路🎈

  1. 清空st[];
  2. 查找节点可否匹配
  3. 如果可以直接匹配返回true,如果不能看看待匹配节点的匹配节点能否移位,如果不能返回flase
  4. 重复1-3

code🎉

bool find(int x){
    for(int i = h[x];i!=-1;i=ne[i]){
        int j = e[i];
        if(!st[j]){
            st[j]=true;
            if(match[j]==0||find(match[j])){
                match[j]=x;return true;
            }
        }
    }
    return false;
}
int res;
for(int i = 1;i<=n;i++){
    memset(st,0,sizeof zt);
    if(find(st[i]))res++;
}

觉得好的话就转发,打赏也不介意😄