UVA 11080 Place The Guards.cpp

#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;
}