Friday, May 27, 2016

uva 10004 - Bicoloring -solution

Unknown
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;

vector <int>v[200];

int bfs(int node)
{
    int color[200]={0};
    int visit[200]={0};
    queue <int> q;
    q.push(node);
    color[node]=1;
    while (!q.empty())
    {
        int f=q.front();
        q.pop();
        int d=color[f]==1?2:1;
        int l=v[f].size();
        for (int i=0;i<l;i++)
        {
            node=v[f][i];
            if (color[f]==color[node]) return 0;
            if (!visit[node])
            {
                q.push(node);
                color[node]=d;
                visit[node]=1;
            }
        }
    }
    return 1;
}

int main()
{
    int n,l,a,b;
    while (1)
    {
        scanf("%d",&n);
        if (n==0) break;
        scanf("%d",&l);
        for (int i=0;i<l;i++)
        {
           scanf("%d%d",&a,&b);
           v[a].push_back(b);
           v[b].push_back(a);
        }
        if (bfs(0)) printf("BICOLORABLE.\n");
        else printf("NOT BICOLORABLE.\n");
        for (int i=0;i<n;i++) v[i].clear();
    }
    return 0;
}

Unknown

Studying at Shahjalal University of Science and Technology, Sylhet.

2 comments:

  1. Vai, int d=color[f]==1?2:1;
    eita dara ki bozai???

    ReplyDelete
  2. int d=color[f]==1?2:1; i don't understand the meaning of this line. can you explain me please??

    ReplyDelete

Coprights @ 2016,