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;
}
0 comments:
Post a Comment