Question
->http://www.spoj.com/problems/BUGLIFE/ In this question we are given number
of bugs and their interactions we have
to check that there should not be
interaction b/w same sex.So basically
we have to check if the graph given is
bipartite or not. I have used the
coloring concept that is if we can
color the graph with the two different
colors then the graph will be
bipartite graph.I tested my code for
many cases it is giving right output
but giving wrong answer on SPOJ.
#include<iostream>
#include<algorithm>
#include<list>
#include<vector>
#include<map>
#include<stdio.h>
#define gc getchar
using namespace std;
void inline input(long int &x)
{
register int c = gc();
x = 0;
for(;(c<48 || c>57);c = gc());
for(;c>47 && c<58;c = gc())
{x = (x<<1) + (x<<3) + c - 48;}
}
int main()
{
long int t,n,in,dup;
map<long int,char> c;
map<long int,char>::iterator j;
multimap<long int,long int> m;
multimap<long int,long int>::iterator i;
input(t); dup=t;
long int u,v;
bool flag;
while(t--)
{
input(n);
input(in);
while(in--)
{
input(u);
input(v);
c[u]='x';//initally all vertices are assigned the null color
c[v]='x';
m.insert(std::pair<long int,long int>(u,v));
}
flag=1;
// b blue color
// g green color
for(i=m.begin();i!=m.end();i++)
{
if(i->first==i->second)
{
flag=0;break; //if self loop not bipartite
}
else if(c[i->first]=='x'&&c[i->second]=='x')
{
c[i->first]='b';
c[i->second]='g';
}
else if(c[i->first]=='x'&&c[i->second]=='b')
{
c[i->first]='g';
}
else if(c[i->first]=='b'&&c[i->second]=='x')
{
c[i->second]='g';
}
else if(c[i->first]=='x'&&c[i->second]=='g')
{
c[i->first]='b';
}
else if(c[i->first]=='g'&&c[i->second]=='x')
{
c[i->second]='b';
}
else if(c[i->first]=='b'&&c[i->second]=='g')
{
continue;
}
else if(c[i->first]=='g'&&c[i->second]=='b')
{
continue;
}
else if(c[i->first]=='b'&&c[i->second]=='b')
{
flag=0;break; //not bipartite
}
else if(c[i->first]=='g'&&c[i->second]=='g')
{
flag=0;break; //not bipartite
}
}
printf("Scenario #%ld:",dup-t);
if(flag)
{
printf("\nNo suspicious bugs found!\n");
}
else
{
printf("\nSuspicious bugs found!\n");
}
m.clear();
c.clear();
}
return 0;
}