学步园

老长时间没做OJ题了,今天心血来潮找一个练练手 1Y  -_-!

题目链接:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=945&mosmsg=Submission+received+with+ID+12530234

题目大意:

输入一个无向图[本题用的bool类型的二维数组保存],用两种颜色给所有结点染色,使其相邻的两个节点颜色不能相同

如果能够成功:

cout << "BICOLORABLE." << endl; 

else

cout << "NOT BICOLORABLE." << endl;

代码如下:

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int MAXN = 205;
int numNode,numPath;
bool vis[MAXN];
bool node[MAXN][MAXN];
bool color[MAXN];
bool ans ;

void init()
{
    memset(vis,0,sizeof(vis));
    memset(node,0,sizeof(node));
    memset(color,0,sizeof(color));
    ans = vis[0] = color[0] = 1;
}

void dfs(int u)
{
    for (int v = 0; v < numNode ; v++)
    {
        if (node[u][v])
        {
            if (!vis[v])
            {
                vis[v] = 1;
                color[v] = !color[u];
                dfs(v);
            }
            else if (color[u] == color[v])
            {
                ans = 0;
                return;
            }
        }
    }
}

int main()
{
    //freopen("input.txt","r",stdin);
    int u,v;
    while (cin >> numNode >> numPath, numNode)
    {
        init();
        for (int i = 0; i < numPath; i++)
        {
            cin >> u >> v;
            node[u][v] = node[v][u] = 1;
        }
        dfs(0);
        if (ans)
            cout << "BICOLORABLE." << endl;
        else
            cout << "NOT BICOLORABLE." << endl;
    }
}