做淘宝客淘宝网站被黑,哪家培训机构好,网站建设教材,毛片a做片在线观看网站什么是二分图#xff1f;
二分图#xff0c;也称作二部图#xff0c;是图论中的一种特殊模型。在一个无向图G(V,E) 中#xff0c;如果顶点集合 V 可以被分割成两个互不相交的子集 A 和 B#xff0c;并且图中的每条边 (i,j) 关联的两个顶点 i 和 j 分别属于这两个不同的顶…什么是二分图
二分图也称作二部图是图论中的一种特殊模型。在一个无向图G(V,E) 中如果顶点集合 V 可以被分割成两个互不相交的子集 A 和 B并且图中的每条边 (i,j) 关联的两个顶点 i 和 j 分别属于这两个不同的顶点集即 i 属于 Aj 属于 B那么这样的图 G 就被称为二分图。二分图有一些特殊的性质和应用例如二分图中不存在奇数长度的环并且它可以用在匹配问题、网络流问题等不同领域。 也就是说二分图就是可以使用两种不同的颜色对图中的顶点进行均匀染色的图例如存在两个区域A、BA与B之间可以通过边进行连接但是A与B内部是没有边的。 二分图当且仅当图中不含奇数环。如果存在奇数环那么就一定不是二分图。因为图中不含奇数环所以染色过程中一定没有矛盾 图示图中1和2表示不同的颜色即二分图里一条边上的两个点的颜色是不尽相同的 题目860. 染色法判定二分图 - AcWing题库 代码
#includeiostream
#includecstring
#includealgorithmusing namespace std;const int N1e510,M2*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 ih[u];i!-1;ine[i]){int je[i];//r如果这一点没有被染色的话那么就对其进行染色if(!color[j]){/*不难发现对其进行染色的过程是在dfs中‘color[u]c;’的这一步*///染色完毕后如果染的颜色与上一个颜色相同则else if语句会返回false//那么就不会形成二分图返回falseif(!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 i0;im;i){int a,b;cin a b;add(a,b),add(b,a);}bool flagtrue;for(int i1;in;i){//如果没有被染色的话if(!color[i]){
//那么就对其进行染色如果dfs返回false那么则二分图不成立if(!dfs(i,1)){//更改标志变量flagfalse;//有一个不成立则二分图整体就不成立break掉即可break;}}}if(flag) puts(Yes);else puts(No);return 0;
}
