首页 > 代码库 > 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 ( $0 \le a < n$).

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 }