题意:

在1976年,四色猜想被一个计算机助手提出,这个理论表示对任意一个地图的上色都只需要四种

颜色,地图内每一个区块和相邻的区块颜色都不相同.

你现在被要求解决一个相似但相对简单的问题.给你任意一个连通的图你必须计算出这个图

是否能够被俩种颜色涂上颜色.意思就是如果一个结点被涂上颜色

(从一个只有俩种颜色的调色板中选取一个颜色),那么相邻的俩个结点都不能有相同的颜色.

为了使问题更加简单,我们保证一下条件.

1：结点不存在自己到自己的边(不存在结点1有条边到结点1)

2：是一个无向图,如果结点a有条边到结点b，可以假设结点b也有条路到结点a

3：是一个强联通图,意思就任意一个结点都有一条路到其他结点.

输入

输入由几组测试用例组成,每一组测试开始的第一行包含一个数字n(1<n<200),表示包含有n个结点.

第二行包含边的数目L,随后L行,每一行包含俩个数字,表示这俩个结点之间有一条边相连接,

图的一个结点使用a标识(0<=a<n)，n=0表示输入结束,不用处理.

输出

看输出用例

 AC时间:0ms

#include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int MAX = 200;void dfs(int r, int *ok, int n, int map[MAX][MAX], int cc, int vis[]){    if(vis[r] == -1)    {        vis[r] = cc;        for(int i = 0; i < n; i++)        {            if(map[r][i] !=-1)            {                map[r][i] = -1;                dfs(i,ok,n,map,(cc+1)%2,vis);            }        }    }    else if(vis[r] !=cc)    {        *ok = 0;    }}int main(){    freopen("d:\\1.txt", "r", stdin);    int n;    string yes = "BICOLORABLE.";    string no = "NOT BICOLORABLE.";    while (cin >> n)    {        if(n == 0)        {            return 0;        }        int l;        cin >> l;        int map[MAX][MAX];        int vis[MAX];        memset(vis, -1, sizeof(vis));        memset(map, -1, sizeof(map));        int s, t;        for(int i = 0; i < l; i++)        {            cin >> s >> t;            map[s][t] = 1;            map[t][s] = 1;        }        int ok = 1;        //深搜        dfs(s, &ok, n, map, 0, vis);        if(ok)            cout << yes << endl;        else            cout << no << endl;    }    return 0;}