LightOj 1009 Back to Underworld

Hints : Bipartite Approach. Just use two colors to mark Vampires and Lycans. Then find who are  maximum . As graph may be disconnected like 

1 5
5 10
8 20

So in this case  1 5, 5 10 And 8 20 are different criteria. That means you have to sum maximum number of both criteria. 


#include <bits/stdc++.h>
using namespace std;
vector<int>edges[20005];
queue<int>q;
long long int color[20005],visited[20005],tn,c,d,x,j,ch,s,i,sum;

int bipartite()
{
    long long int k,fr;
    sum=0;
    for(tn=1;tn<=20005;tn++)
    {
        ch=edges[tn].size();
        c=0;
        d=0;
        if(visited[tn]==0 && ch>=1)
        {
            s=tn;
            color[s]=1;
            d=d+1;
            //cout<<s<<"<==1=>>"<<d<<endl;
            q.push(s);
            visited[s]=1;

            while(!q.empty())
            {
                fr=q.front();

                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];
                         if(color[edges[fr][k]]==0)
                         {
                             c++;
                             //cout<<edges[fr][k]<<"<==0=>>"<<c<<endl;

                         }
                         else if(color[edges[fr][k]]==1)
                         {
                             d++;
                             //cout<<edges[fr][k]<<"<==1=>>"<<d<<endl;
                         }

                    }


                }
                q.pop();
                x=max(c,d);


            }
                //cout<<x<<endl;
                sum=sum+max(c,d);
        }

    }




}


int main()
{
    long long int e,p,n,u,v,f,m,t,z,y,tf;
    //freopen("1009.txt","r",stdin);
    //freopen("1009out.txt","w",stdout);
    cin>>t;
    for(y=1;y<=t;y++)
    {
        cin>>e;
        memset(edges,0,sizeof edges);
        memset(visited,0,sizeof visited);
        memset(color,-1,sizeof color);
        for(tf=0;tf<e;tf++)
        {
            cin>>u>>v;
            edges[u].push_back(v);
            edges[v].push_back(u);


        }
        bipartite();

        cout<<"Case "<<y<<": "<<sum<<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