UVA 11080 Place the Guards





Hints : It's a Bipartite Checking problem but there are some tricky cases. Some Nodes May be disconnected, so it's important to place that bipartite checking function inside a loop that will traverse all vertices. Next if nodes are totally isolated from other nodes and are not included in the inputs then they are not visited. so if some nodes are not visited count them. Consider Minimum Number Of Guards.



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

int bipartite(int s)
{
    int k,fr;
    memset(color,-1,sizeof color);
    color[s]=1;
    while(!q.empty())
    {
        q.pop();
    }
    q.push(s);
    d=1;
    c=0;
    visited[s]=1;
    while(!q.empty())
    {
        fr=q.front();
        s=edges[fr].size();
        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++;
                 }
                 else if(color[edges[fr][k]]==1)
                 {
                     d++;
                 }

            }


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

            }

        }
        q.pop();
        if(q.empty())
        {
            if(c==0)
            {
                x=d;
            }
            else if(d==0)
            {
                x=c;
            }
            else
            {
               x=min(c,d);
            }



        }


    }
    return true;
}


int main()
{
    int i,e,p,n,u,v,f,m,t,z,y;
    //freopen("11080.txt","r",stdin);
    //freopen("11080out.txt","w",stdout);
    cin>>t;
    while(t--)
    {
        cin>>tn;
        cin>>e;
        for(z=0;z<tn;z++)
        {
             visited[z]=0;
        }
        memset(edges,0,sizeof edges);
        item.clear();
        c=0;
        d=0;
        sum=0;
        y=0;
        for(i=0;i<e;i++)
        {
            cin>>u>>v;
            edges[u].push_back(v);
            edges[v].push_back(u);
        }
        if(bipartite(0)==false)
        {
            cout<<"-1"<<endl;
            y=1;
        }
        for(z=0;z<tn;z++)
        {
             visited[z]=0;
        }
        if(y!=1)
        {
          x=0;
          for(i=0;i<tn;i++)
          {

            for(j=0;j<edges[i].size();j++)
            {

                if(visited[edges[i][j]]==0)
                {
                    bipartite(i);
                    sum=sum+x;

                }


            }

        }
         for(i=0;i<tn;i++)
         {
             if(visited[i]==0)
             {
                 sum++;
             }
          }

          if(e==0)
          {
              cout<<tn<<endl;
          }
          else
          {
             cout<<sum<<endl;
          }
        }




    }

    return 0;
}


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
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment