首页 > 代码库 > UVA 10004 Bicoloring
UVA 10004 Bicoloring
题目链接: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即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #include<vector> 8 #define inf 0x7fffffff 9 #define exp 1e-1010 #define PI 3.14159265411 using namespace std;12 const int maxn=222;13 int color[maxn];14 vector<int> G[maxn];15 int bi(int u)16 {17 int k=G[u].size();18 for (int i=0 ;i<k ;i++)19 {20 int v=G[u][i];21 if (!color[v])22 {23 color[v]=3-color[u];24 if (!bi(v)) return false;25 }26 if (color[v]==color[u]) return false;27 }28 return true;29 }30 int main()31 {32 int n,l;33 while (scanf("%d",&n)!=EOF)34 {35 if (!n) break;36 scanf("%d",&l);37 for (int i=0 ;i<=n ;i++) G[i].clear();38 memset(color,0,sizeof(color));39 int a,b;40 for (int i=0 ;i<l ;i++)41 {42 scanf("%d%d",&a,&b);43 G[a].push_back(b);44 G[b].push_back(a);45 }46 color[1]=1;47 int flag=bi(1);48 if (flag) cout<<"BICOLORABLE."<<endl;49 else cout<<"NOT BICOLORABLE."<<endl;50 }51 return 0;52 }