新农村建设管理网站,重庆沙坪坝火车站,北京搜索引擎优化管理专员,wordpress例模拟染色#xff0c;因为只有两种颜色#xff0c;所以分别用 0、 1 代表这两种颜色#xff0c;然后从0开始深搜#xff0c;如果 每个点都能染上色#xff0c;且相邻两点的颜色不同#xff0c;则符合要求。 #includestdio.h#includestring.h#define MAXN …模拟染色因为只有两种颜色所以分别用 0、 1 代表这两种颜色然后从0开始深搜如果 每个点都能染上色且相邻两点的颜色不同则符合要求。 #includestdio.h#includestring.h#define MAXN 210int map[MAXN][MAXN];int paint[MAXN];int u, v, M, N;bool dfs( int i, int color){for( int j 0; j N; j ) {if( map[i][j]) {if( paint[j] ! -1 paint[j] ! color)return false;else if( paint[j] - 1) { paint[j] color;if( !dfs( j, 1 - color)) //用 0和1分别代表白‘黑两种颜色 return false; } } }return true;}void init(){ scanf( %d, M); memset( map, 0, sizeof map);for( int i 0; i M; i ) { scanf( %d%d, u, v); map[u][v] map[v][u] true; } memset( paint, -1, sizeof paint); paint[0] 1;// 如果这里等于0的话则dfs( 0, 1)。}int main(){while( scanf( %d, N), N) { init();if( dfs( 0, 0)) printf( BICOLORABLE.\n);else printf( NOT BICOLORABLE.\n); }return 0;} 转载于:https://www.cnblogs.com/Yu2012/archive/2011/12/06/2278372.html
