UVa 10004 二染色
题意：给定一个无向图，是强连通的，而且无自回路。对顶点进行染色，相邻的顶点需要用不同的颜色，但总共只有两种颜色，是否可行。
思路：二部图的判定。其实通过题意思考，也可以发现，如果没有回路是可以的，如果有回路，而回路的顶点个数是偶数个也是可以的，是奇数个则不行。而这正是二部图的充要条件：无向图的所有回路长度都为偶数。 但这里如何判断回路长度不好实现。 这里的思路是，对图进行遍历，dfs或bfs都可以，在遍历的过程中进行染色，当发现冲突时即不可行。
Code：
#include
#includebool dfs(int k,int n);int graph[210][210];
int vis[210];
int color[210];int main()
{//freopen("10004.in","r",stdin);//freopen("10004.out","w",stdout);int n,nl;while(scanf("%d%d",&n,&nl)==2 && n){memset(graph,0,sizeof(graph));memset(vis,0,sizeof(vis));int i,j;for(int k=0;k 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！