当前没有测试数据。

二分图概念

二分图又叫二部图，是图论中的一种特殊模型。

假设S=(V,E)是一个无向图。如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，就可以称图S为一个二分图。  简单来说，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。

二分图的判定

判断一个图是否是二分图，可以直接DFS+染色即可。

[!note] 先将一个点染色为颜色c，然后搜索邻接点，将邻接点染色为相反颜色，如果某个点的邻接点已经被染色且和他颜色一致，则返回false，如果邻接点颜色失败，也返回false，染色完毕没有问题返回true。

int color[MAXN];  
bool dfs(int v,int c){//将点v染色c  
    color[v]=c;  
    for(int i=0;i<mp[v].size();i++){  
        if(color[mp[v][i]]==c)             return false;  
        if(color[mp[v][i]==0 && !dfs(mp[v][i],-c))             return false;  
        //如果点v的邻接点没有染过色且此次染色失败 返回false，加上逻辑非if成立 返回false
    }  
    return true;  
}

二分图判定 - 题目详情 - 知码开花OJ