染色法判定二分图

什么是二分图？

二分图，也称作二部图，是图论中的一种特殊模型。在一个无向图G=(V,E) 中，如果顶点集合 V 可以被分割成两个互不相交的子集 A 和 B，并且图中的每条边 (i,j) 关联的两个顶点 i 和 j 分别属于这两个不同的顶点集（即 i 属于 A，j 属于 B），那么这样的图 G 就被称为二分图。二分图有一些特殊的性质和应用，例如，二分图中不存在奇数长度的环，并且它可以用在匹配问题、网络流问题等不同领域。
也就是说：二分图，就是可以使用两种不同的颜色对图中的顶点进行均匀染色的图，例如：存在两个区域A、B，A与B之间可以通过边进行连接，但是A与B内部是没有边的。
二分图，当且仅当图中不含奇数环。如果存在奇数环，那么就一定不是二分图。因为图中不含奇数环，所以染色过程中一定没有矛盾
图示：图中1和2表示不同的颜色，即二分图里一条边上的两个点的颜色是不尽相同的
             

 题目：860. 染色法判定二分图 - AcWing题库

 代码：

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N=1e5+10,M=2*N;
int e[M],h[N],ne[M],idx;
int n,m,color[N];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;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];//r如果这一点没有被染色的话，那么就对其进行染色if(!color[j]){/*不难发现，对其进行染色的过程是在dfs中‘color[u]=c;’的这一步*///染色完毕后，如果染的颜色与上一个颜色相同，则else if语句会返回false//那么就不会形成二分图，返回false；if(!dfs(j,3-c)) return false;}//如果该颜色与上一个颜色相同，则二分图不成立else if(color[j]==c) return false;}return true;
}int main()
{cin >> n >> m;memset(h,-1,sizeof h);for(int i=0;i<m;i++){int a,b;cin >> a >> b;add(a,b),add(b,a);}bool flag=true;for(int i=1;i<=n;i++){//如果没有被染色的话if(!color[i]){
//那么就对其进行染色，如果dfs返回false，那么则二分图不成立if(!dfs(i,1)){//更改标志变量flag=false;//有一个不成立，则二分图整体就不成立，break掉即可break;}}}if(flag) puts("Yes");else puts("No");return 0;
}