怎样创建网站或网页,怎样在国外网站上做外贸广告,企业网站建立模板怎么做,厦门建设工程信息网一个图是二分图当且仅当这个图中不含奇数环
由于图中没有奇数环#xff0c;所以染色过程中一定没有矛盾
所以一个二分图一定可以成功被二染色#xff0c;反之在二染色的过程中出现矛盾的图中一定有奇数环#xff0c;也就一定不是二分图
#includeiostream
#includ…一个图是二分图当且仅当这个图中不含奇数环
由于图中没有奇数环所以染色过程中一定没有矛盾
所以一个二分图一定可以成功被二染色反之在二染色的过程中出现矛盾的图中一定有奇数环也就一定不是二分图
#includeiostream
#includealgorithm
#includecstringusing namespace std;const int N 100010, M 200010;int n, m;
int h[N], e[M], ne[M], idx;
int color[N]; //color[i]代表i点有没有被染色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; //记录当前点的颜色是cfor(int i h[u]; i ! -1; i ne[i])//遍历当前点的邻点{int j e[i];if(!color[j]) //如果该点没有被染色{if(!dfs(j, 3 - c)) return false; //有1、2两种颜色,3-12,3-21,能把邻点染成与u点不同的颜色}else if(color[j] c) return false; //如果u的邻点的颜色等于u的颜色}return true;
}int main()
{cin n m;memset(h, -1, sizeof h);while(m -- ){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]) //如果该点没有被染色{if(!dfs(i, 1)) //如果bfs i点时返回false{flag false;break;}}}if(flag) cout Yes endl;else cout No endl;return 0;
}
