UVA 10004 - Bicoloring(cpp file)

Problem Type : Graph Using BFS Algorithm



#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
vector <int > vcc1;

int mat[300][300],q[100000],cost[100000],color[100000];
void bfs(int node , int start)
{
    int i,j,f,r,u,s,coun =0;
    f = r = 0;
    q[r++]=start;
    color[start] = 1;
    cost[start]=0;
    vcc1.push_back(cost[start]);
    s=0;
    while(f!=r)
    {
       u=q[f++];


        for(i=0;i<node;i++)
        {
            if(mat[u][i]==1 && color[i]==0)
            {
              color[i]=1;
               q[r++]=i;
              cost[i]= cost[u]+1;
              vcc1.push_back(cost[i]);
            }
        }
    }
    coun =0;
    for(i=0;i<vcc1.size();i++)
    {
       for(j=i+1;j<=vcc1.size();j++)
       {
           if(cost[i]==cost[j] && mat[i][j]==1)
           {
               coun =1;
           }
       }
    }
    if(coun == 1)
    {
        cout << "NOT BICOLORABLE." << endl;
    }
    else
    {
        cout << "BICOLORABLE." <<endl;
    }

}
int main()
{
 int n,i,e,ed,v,start;
while(scanf("%d",&n)==1)
{
    vcc1.clear();
   // vcc2.clear();
    memset(mat,0,sizeof(mat));
    memset(color,0,sizeof(color));
    memset(cost,0,sizeof(cost));
     memset(q,0,sizeof(q));
    if(n==0)
        break;
    scanf("%d",&e);
    for(i=1;i<=e;i++)
    {
        scanf("%d %d",&v,&ed);
        if(i==1)
        {
            start=v;
        }
        mat[v][ed]=1;
        mat[ed][v]=1;
    }
    bfs(n,start);

}

}