UVa problem solution 10004 - Bicoloring

problem link:

Discuss: if you know bfs algorithm then this problem is fun for you. just do bfs nothing more to do.just first take a color array as like visiting array. convert all number to zero.then in while loop if the color is zero and adjacent node color is then assign it with 2 else 1. and if two adjacent node color same then just break the loop.

try yourself before see the code




#include<bits/stdc++.h>
using namespace std;
int main()
{
    int node;
    while(cin >>node&&node)
    {
        int edge,a,s,b,i,j,cnt=0,flag=0;
        cin >>edge;
        int N=edge+5;
        vector<int>vec[N];
        queue<int>que;
        bool visit[N];
        int color[N];
        memset(visit,false,sizeof visit);
        memset(color,0,sizeof color);
        for(i=0;i<edge;i++)
        {
            cin >>a>>b;
            vec[a].push_back(b);
            vec[b].push_back(a);
        }
        que.push(0);
        visit[0]=true;
        color[0]=1;
        while(!que.empty())
        {
            int x=que.front();
            que.pop();
            int sz=vec[x].size();
//            if(vec[x][x]==1)
//                flag=1;
            for(i=0;i<sz;i++)
            {
                int y=vec[x][i];
                if(color[y]==0)
                {
                    if(color[x]==1)
                    color[y]=2;
                    else
                        color[y]=1;

                        que.push(y);
                }
              else if(color[x]==color[y])
                    flag=1;
            }
        }
        if(flag)
            cout <<"NOT BICOLORABLE."<<endl;
        else
            cout <<"BICOLORABLE."<<endl;
    }
    return 0;
}