二分图的判断

• 什么是二分图
• 如何证明一个图是二分图
• 代码

什么是二分图

如果一个无向图？ 能够将顶点被划分为两瓣 ，且每一瓣中的顶点都没有边，即为二分图。
也就是说，二分图一定不存在奇数条边的连通图。

如何证明一个图是二分图

染色法，用bfs或者dfs来给每一个点染色，如果遇到了下一个点的颜色等于这一个点的颜色，即可确定这不是一个二分图。

代码

参考y总的dfs模板

时间复杂度是 O(n+m)O(n+m), nn 表示点数，mm 表示边数  
int n;      // n表示点数  
int h[N], e[M], ne[M], idx;     // 邻接表存储图  
int color[N];       // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色  
  
// 参数：u表示当前节点，c表示当前点的颜色  
bool dfs(int u, int c)  
{  
    color[u] = c;  
    for (int i = h[u]; i != -1; i = ne[i])  
    {  
        int j = e[i];  
        if (color[j] == -1)  
        {  
            if (!dfs(j, !c)) return false;  
        }  
        else if (color[j] == c) return false;  
    }  
  
    return true;  
}  
  
bool check()  
{  
    memset(color, -1, sizeof color);  
    bool flag = true;  
    for (int i = 1; i <= n; i ++ )  
        if (color[i] == -1)  
            if (!dfs(i, 0))  
            {  
                flag = false;  
                break;  
            }  
    return flag;  
}  
  
作者：yxc  
链接：https://www.acwing.com/blog/content/405/  
来源：AcWing  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。