UVA 11396 Claw Decomposition

#include <bits/stdc++.h>
using namespace std;
vector<int>edges[1000];
queue<int>q;
int color[1000],visited[1000],tn;

int bipartite(int s)
{
    int j,k,fr;
    memset(color,-1,sizeof color);
    color[s]=1;
    while(!q.empty())
    {
        q.pop();
    }
    q.push(s);
    for(j=1;j<=tn;j++)
    {
        visited[j]=0;
    }
    visited[s]=1;
    while(!q.empty())
    {
        fr=q.front();

        //cout<<"Size Of "<<fr<<"="<<edges[fr].size()<<endl;

        for(k=0;k<edges[fr].size();k++)
        {
            if(visited[edges[fr][k]]==0 && color[edges[fr][k]]==-1)
            {
                 q.push(edges[fr][k]);
                 visited[edges[fr][k]]=1;
                 color[edges[fr][k]]=1-color[fr];

            }


        }
        for(k=0;k<edges[fr].size();k++)
        {
            if(visited[edges[fr][k]]==1 && color[edges[fr][k]]==color[fr])
            {
                return false;

            }

        }

        q.pop();
    }
    return true;
}


int main()
{
    int i,e,p,n,u,v,f,m,t,y;
    //freopen("11396.txt","r",stdin);
    //freopen("11396out.txt","w",stdout);
    while(1)
    {
        cin>>tn;
        e=(tn*3)/2;
        if(tn==0)
        {
            break;
        }
        memset(edges,0,sizeof edges);

        while(1)
        {
            cin>>u>>v;
            if(u==0 && v==0)
            {
                break;
            }
            edges[u].push_back(v);
            edges[v].push_back(u);
        }

        if(bipartite(1))
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }

    return 0;
}

Download Coding Interview Book and Get More Tutorials for Coding and Interview Solution: Click Here

Download System Design Interview Book and Get More Tutorials and Interview Solution: Click Here

Do you need more Guidance or Help? Then Book 1:1 Quick Call with Me: Click Here

Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge. Learn More: Click Here