题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=945

Problem:In 1976 the ``Four Color Map Theorem" was proven with the assistance of a computer. This theorem states that every map can be colored using only four colors, in such a way that no region is colored using the same color as a neighbor region.

Here you are asked to solve a simpler similar problem. You have to decide whether a given arbitrary connected graph can be bicolored. That is, if one can assign colors (from a palette of two) to the nodes in such a way that no two adjacent nodes have the same color. To simplify the problem you can assume:

  • no node will have an edge to itself.
  • the graph is nondirected. That is, if a node a is said to be connected to a node b, then you must assume that b is connected to a.
  • the graph will be strongly connected. That is, there will be at least one path from any node to any other node.

Input:The input consists of several test cases. Each test case starts with a line containing the number n ( 1 < n< 200) of different nodes. The second line contains the number of edges l. After this, l lines will follow, each containing two numbers that specify an edge between the two nodes that they represent. A node in the graph will be labeled using a number a ( ).

An input with n = 0 will mark the end of the input and is not to be processed.

Output:You have to decide whether the input graph can be bicolored or not, and print it as shown below.

解法:判断是否可以二分染色。直接dfs即可。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#define inf 0x7fffffff
#define exp 1e-10
#define PI 3.141592654
using namespace std;
const int maxn=;
int color[maxn];
vector<int> G[maxn];
int bi(int u)
{
int k=G[u].size();
for (int i= ;i<k ;i++)
{
int v=G[u][i];
if (!color[v])
{
color[v]=-color[u];
if (!bi(v)) return false;
}
if (color[v]==color[u]) return false;
}
return true;
}
int main()
{
int n,l;
while (scanf("%d",&n)!=EOF)
{
if (!n) break;
scanf("%d",&l);
for (int i= ;i<=n ;i++) G[i].clear();
memset(color,,sizeof(color));
int a,b;
for (int i= ;i<l ;i++)
{
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
color[]=;
int flag=bi();
if (flag) cout<<"BICOLORABLE."<<endl;
else cout<<"NOT BICOLORABLE."<<endl;
}
return ;
}

最新文章

  1. 将Oracle数据库中的数据写入Excel
  2. XE3随笔15:使用 IXMLHTTPRequest 简单获取网页源代码
  3. mybatis异常
  4. android向web提交参数的4种方式总结,附带网站案例源码
  5. HTML5自带的原生定位
  6. 【Away3D代码解读】其它一些的记录(持续更新)
  7. 文件服务&mdash;&mdash;Vsftpd
  8. Nginx的HTTP模块
  9. (摘录)MSMQ的简单介绍
  10. 【CSS学习笔记】背景图片
  11. 3. JavaScript 数据类型
  12. 2018-2019-2 20175235 实验二《Java面向对象程序设计》实验报告
  13. windows 7 安装时提示:安装程序无法创建新的系统分区
  14. ACM学习之路
  15. mybatis generator的maven插件,找不到properties的配置文件错误的解决
  16. arm irq system
  17. Codeforces 838A - Binary Blocks(二维前缀和+容斥)
  18. composer install 出现的问题
  19. 寻找List之和的最近素数
  20. spark中利用Sql2o连接数据的例子BlogService

热门文章

  1. 做fzu oj 1045 做减法学到的sprintf()函数
  2. 255. Verify Preorder Sequence in Binary Search Tree
  3. POJ3581---Sequence 后缀树组
  4. 程序员使用Node的十个技巧
  5. qt 4.6.2 vs 2005 + QCreator 开发环境配置(有注册码)
  6. CCTableView 简单样例
  7. USACO Milk2 区间合并
  8. AxonVR:体验有触觉有温度的VR世界
  9. 在SQL Server里如何处理死锁
  10. Tomcat 对 HTTP 协议的实现(下)
  11. python 爬虫与数据可视化--matplotlib模块应用
  12. Elasticsearch单机双节点集群部署实战
  13. 怎么清理Linux系统磁盘空间占用大:/dev/xvda1
  14. thinkphp 5 使用oss
  15. Kubernetes---DaemonSet
  16. 机器学习入门01 - 框架处理(Framing)
  17. python之路--关于线程的一些方法
  18. dubbo监控中心---dubbo-admin
  19. Vue2.0学习——axios用法详解
  20. JS实例4