图论 - 二分图（染色法、匈牙利算法）

文章目录

• 前言
• Part 1：染色法判定二分图
• • 1.题目描述
  • • • 输入格式
      • 输出格式
      • 数据范围
      • 输入样例
      • 输出样例
      • 2.算法
      • Part 2：匈牙利算法求二分图的最大匹配
      • • 1.题目描述
        • • • 输入格式
            • 输出格式
            • 数据范围
            • 输入样例
            • 输出样例
            • 2.���法

              前言

              本篇博客将介绍两种二分图有关的算法，分别是染色法判定二分图和匈牙利算法求二分图的最大匹配。那么我们先要知道什么是二分图？

              二分图：有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中，每个顶点集中没有边直接相连接。也就是：图中点通过移动能分成左右两部分，左侧的点只和右侧的点相连，右侧的点只和左侧的点相连。如下图：

              Part 1：染色法判定二分图

              1.题目描述

              给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。

              请你判断这个图是否是二分图。

              输入格式

              第一行包含两个整数 n 和 m。

              接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。

              输出格式

              如果给定图是二分图，则输出 Yes，否则输出 No。

              数据范围

              1≤n,m≤105

              输入样例

              4 41 31 42 32 4

              输出样例

              Yes

              2.算法

              • 开始对任意一未染色的顶点染色
              • 判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色（因为二分为两个顶点集合，所以一共两种颜色，分别用1和2代替）
              • 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断
              • 用DFS即可

                #include #include #include using namespace std;const int N = 100010 * 2;int e[N], ne[N], idx;//邻接表存储图int h[N];int color[N];//保存各个点的颜色，0 未染色，1 是红色，2 是黑色int n, m;//点和边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;//u的点成 c 染色    //遍历和 u 相邻的点    for(int i = h[u]; i!= -1; i = ne[i])    {        int b = e[i];                           if(!color[b])//相邻的点没有颜色,则递归处理这个相邻点        {            if(!dfs(b, 3 - c)) return false;//（3 - 1 = 2， 如果 u 的颜色是2，则和 u 相邻的染成 1）                                            //（3 - 2 = 1， 如果 u 的颜色是1，则和 u 相邻的染成 2）        }        else if(color[b] && color[b] != 3 - c)//如果已经染色，判断颜色是否为 3 - c        {                                                 return false;//如果不是，说明冲突，返回                           }    }    return true;}int main(){    memset(h, -1, sizeof h);//初始化邻接表    cin >> n >> m;    for(int i = 1; i > a >> b;        add(a, b), add(b, a);    }    for(int i = 1; i > m;        // 保存图，因为只从一遍找另一边，所以该无向图只需要存储一个方向    for(int i = 0; i > a >> b;        add(a, b);    }        int res = 0;    //为各个点找匹配    for(int i = 1; i