1 / 3
Aug 2019

#include
#include <bits/stdc++.h>
using namespace std;

vector<vector> a(1000001);
vector v;
vector co;
queue q;

bool bfs(int t)
{q.push(t);
v[t]=1;
co[t]=1;
while(!q.empty())
{int p=q.front();
int c=co[p];
q.pop();

for(int i=0;i<a[p].size();i++)
{if(v[a[p][i]]!=1)
{v[a[p][i]]=1;
q.push(a[p][i]);
if(co[a[p][i]]==-1)
{co[a[p][i]]=1-c;}
else
{if(co[a[p][i]]==c)return 0;}

    }
  else
    {if(co[a[p][i]]==c)return 0;}
 	
 }

}
return 1;

}

int main() {
int t;
cin>>t;
int c=1;
while(t–)
{long long n,ni;
cin>>n>>ni;

 if(n==1)
 {cout<<"Scenario #"<<c<<":\n";
 cout<<"No suspicious bugs found!\n";
 	continue;
 }
 
 v.clear();
 co.clear();
 for(int i=0;i<=n;i++)
    {a[i].clear();
     v.push_back(0);
     co.push_back(-1);
    }
 //v.push_back(0);
 //co.push_back(-1);	

for(int i=0;i<ni;i++)
{int x,y;
 cin>>x>>y;
 a[x].push_back(y);
 a[y].push_back(x);
	
}

bool b=1;

for(int i=1;i<=n;i++)
{if(co[i]==-1)
   {b=b&bfs(i);}
}


if(b==0)
  {cout<<"Scenario #"<<c<<":\n";
   cout<<"Suspicious bugs found!\n";
  }
else
{
 cout<<"Scenario #"<<c<<":\n";
 cout<<"No suspicious bugs found!\n";
	
}
	
	c++;
	
}




return 0;

}

  • created

    Aug '19
  • last reply

    Aug '19
  • 2

    replies

  • 608

    views

  • 2

    users

  • 1

    link

Link to BugLife2.

Here are two test cases that describe the same set of interactions, yet your code gives a different answer for each.

2
3 3
1 2
1 3
2 3
3 3
1 2
1 3
3 2

It’d be a great help in future if you’d blockquote when pasting code, so I don’t have to fix all the compilation problems that get created otherwise. Please.

Thanks for the help. Just had to declare the queue inside the bfs function.
And sorry for the inconvenience :sweat_smile: