二分图相关算法模板

二分图判定

算法思路

/**
 * 每个点有两种状态，对于每种状态采取不同的策略
 * 1.未染色
 *   将该点及其子节点染色
 * 2.已染色
 *   判断是否出现冲突，是则说明不是二分图
 * 
 * 二分图就是不包含奇数环的图 或者说 有两个集合a 和 b，对于一条边的两个点一个分到a，一个分到b，所以如果想要满足二分图，一条边的两个顶点必须分到不同的集合
 * 把分到集合a看为染色为a，分到集合b看为染色为b，包含奇数环一定有某个点即被染色为a又被染色为b，这种情况称之为冲突，二分图就是任何一个点的染色都是唯一的，不会存在冲突
 * 所以代码实现就是判断在染色过程中是否出现了某个点的染色出现了冲突，而染色过程就是遍历过程，遍历就可以采用dfs和bfs
 * 
 * 从数据结构来看是稀疏图，且算法对存储结构并没有明显的要求(bellman_ford明确需要遍历边，所以采用结构体存边)，所以采用邻接表存储
 */

dfs版本

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

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

void insert(int a, int b)
{
    e[idx] = b;
    ne[idx] = head[a];
    head[a] = idx ++;
}
bool dfs(int x, int v)
{
    color[x] = v;
    
    for (int i = head[x]; i != -1; i = ne[i])
    {
        int p = e[i];
        if (color[p] == -1)
        {
            if (!dfs(p, 1 ^ v)) return false; 
        }
        else if (color[p] == color[x]) return false;
    }
    
    return true;
}
int main()
{
    cin >> n >> m;
    
    memset(head, -1, sizeof head);
    memset(color, -1, sizeof color);
    
    while (m --)
    {
        int a, b;
        cin >> a >> b;
        insert(a, b);
        insert(b, a);
    }
    
    bool flag = true;
    for (int i = 1; i <= n; ++ i)
        if (color[i] == -1)
        {
            if (!dfs(i, 0)) // 如果i号点没有染色，那么递归将这一条路上的所有点都染色，如果染色过程中不是二分图，则返回false
            {
                flag = false;
                break;
            }
        }
        
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}

bfs版本

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2e5 + 10; // 第一次写的1e5+10超时了，问题是本题是无向图，所以一条边需要2个存储空间，所以要翻倍

int n, m;
int color[N]; // -1表示未染色 0 和 1 表示两种不同的颜色
int head[N], e[N], ne[N], idx;

void insert(int a, int b)
{
 e[idx] = b;
 ne[idx] = head[a];
 head[a] = idx ++;
}
int main()
{
 cin >> n >> m;
 
 memset(head, -1, sizeof head);
 memset(color, -1, sizeof color);
 
 while (m --)
 {
     int a, b;
     cin >> a >> b;
     insert(a, b);
     insert(b, a); // 无向图，一定不要忘了
 }
 
 queue<int> q;
 bool flag = true;
 // 并没有保证一定为连通图，所以为了遍历到所有点需要从每一个点开始一次
 for (int i = 1; i <= n; ++ i)
 {
     if (color[i] != -1) continue; // 点i已经被染色就不再考虑了

     q.push(i);
     color[i] = 0;
     while (q.size())
     {
         int t = q.front();
         q.pop();
         for (int i = head[t]; i != -1; i = ne[i])
        {
            int p = e[i];
            if (color[p] == -1)
            {
                color[p] = 1 ^ color[t]; // 0 -> 1; 1 -> 0
                q.push(p);
            }
            else if (color[p] == color[t])
            {
                flag = false;
                break;
            }
        }
        if (!flag) break;
     }
     if (!flag) break;
 }

 if (flag) cout << "Yes" << endl;
 else cout << "No" << endl;
 
 return 0;
}

二分图最大匹配---匈牙利算法

算法思想

二分图相关算法模板

原文：https://www.cnblogs.com/G-H-Y/p/14351040.html