Monday, August 22, 2016

Uva 10004 - Bicoloring

#include<bits/stdc++.h>
using namespace std;
vector<int>adj[1000];
queue<int>q;
int color[1000] , visited[1000];
bool isBipertite(int s)
{
     memset(color,-1,sizeof(color));
     color[s] = 1;
    while(!q.empty())
    {
        q.pop();
    }
    int fr;
    q.push(s);
    memset(visited,0,sizeof(visited));
    visited[s] = 1;
    while(!q.empty()){
        fr = q.front();
        q.pop();
        for(int k=0; k<adj[fr].size(); k++){
            if(visited[adj[fr][k]]==0 && color[adj[fr][k]]==-1){
                 q.push(adj[fr][k]);
                visited[adj[fr][k]] = 1;
                color[adj[fr][k]] = 1 - color[fr];
            }
        }
        for(int i=0; i<adj[fr].size(); i++){
            if(visited[adj[fr][i]]==1 && color[adj[fr][i]] == color[fr]) return false;
        }
    }

   return true;
}
int main()
{
     int node  , e;
     while(cin>>node &&node){
        cin>>e;
        memset(adj,0,sizeof (adj));
        for(int i=0; i<e; i++){
            int u , v;
            cin>>u>>v;
            adj[u].push_back(v);
        }
        isBipertite(0) ? cout<<"BICOLORABLE.\n" : cout<<"NOT BICOLORABLE.\n";
     }

    return 0;
}

No comments:

Post a Comment