UVA 10004 Bicoloring
8841 ワード
テーマリンク：http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=12&page=show_problem&problem=945
Problem:In 1976 the`Four Color Map Themom"was proven with the assistance of a coputer.This theorm states that evermap can be colored using only colors，in such a way that no region colored coloregion therese。
Here you are asked to solive a simpler simillar proble.You have to decide whether a given arbitrary connected graph can be bicolored.That is，if one can assign colors
の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 asume that b is connected to a. the graph will be stronigly 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 follows、each containing two numbers that specify an edge between the two nodes that the y represent.A node in the grapph 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でいいです。
Problem:In 1976 the`Four Color Map Themom"was proven with the assistance of a coputer.This theorm states that evermap can be colored using only colors，in such a way that no region colored coloregion therese。
Here you are asked to solive a simpler simillar proble.You have to decide whether a given arbitrary connected graph can be bicolored.That is，if one can assign colors
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-10
10 #define PI 3.141592654
11 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 }