Algorithm
Problem link- https://www.spoj.com/problems/BUGLIFE/
BUGLIFE - A Bug’s Life
Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers were printed on their backs.
Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs or if it contains some bug interactions that falsify it.
Input
The first line of the input contains the number of scenarios. Each scenario starts with one line giving the number of bugs (at least one, and up to 2000) and the number of interactions (up to 1000000) separated by a single space. In the following lines, each interaction is given in the form of two distinct bug numbers separated by a single space. Bugs are numbered consecutively starting from one.
Output
The output for every scenario is a line containing “Scenario #i:”, where i is the number of the scenario starting at 1, followed by one line saying either “No suspicious bugs found!” if the experiment is consistent with his assumption about the bugs’ sexual behavior, or “Suspicious bugs found!” if Professor Hopper’s assumption is definitely wrong.
Example
Input: 2 3 3 1 2 2 3 1 3 4 2 1 2 3 4 Output: Scenario #1: Suspicious bugs found! Scenario #2: No suspicious bugs found!
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define MOD (ll)1000000007
#define pb push_back
#define EPS 1e-9
#define FOR(i, n) for(int i = 0;i < n; i++)
#define si(a) scanf("%d", &a)
#define pi(a) printf("%d\n", a)
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
const int MAXN = 2e3+5;
vector<int> adj[MAXN];
int color[MAXN];
int checkBipartiteComponent(int source){
queue<int> que;
que.push(source);
// color[source] = 1;
while(!que.empty()){
int vertex = que.front();
// cout<<vertex<<' '<<color[vertex]<<endl;
que.pop();
for(int i = 0;i < adj[vertex].size(); i++){
int adjacent = adj[vertex][i];
// cout<<adjacent<<endl;
if(color[adjacent] == 0){
if(color[vertex] == 1)
color[adjacent] = -1;
else
color[adjacent] = 1;
que.push(adjacent);
}
else if(color[adjacent] == color[vertex])
return 0;
}
}
// cout<<"HELO"<<endl;
return 1;
}
int main(){
int sce;
si(sce);
for(int i = 1; i<= sce; i++){
int n;
si(n);
int se;
si(se);
memset(color, 0, sizeof(color));
for(int j = 1; j < MAXN; j++){
adj[j].clear();
}
for(int j = 1;j <= se; j++){
int a, b;
si(a);
si(b);
adj[a].pb(b);
adj[b].pb(a);
}
// color[1] = 1;
// cout<<checkBipartiteComponent(1)<<endl;
int res = 1;
for(int j = 1;j <= n; j++){
if(color[j] == 0){
color[j] = 1; //color[i] = 1 indicates it is red.
// cout<<res<<endl;
res = res & checkBipartiteComponent(j);
}
}
printf("Scenario #%d:\n", i);
if(!res){
printf("Suspicious bugs found!\n");
}else{
printf("No suspicious bugs found!\n");
}
}
return 0;
}Input
3 3
1 2
2 3
1 3
4 2
1 2
3 4
Output
Suspicious bugs found!
Scenario #2:
No suspicious bugs found!
#2 Code Example with Java Programming
Code -
Java Programming
import java.io.*;
import java.util.*;
public class buglife
{
private static Reader in;
private static PrintWriter out;
private static ArrayList <Integer> [] connect;
private static int[] color;
public static void main (String [] args) throws IOException {
in = new Reader ();
out = new PrintWriter (System.out, true);
int t = in.nextInt (), n, m, i, a, b, j=0;
while (t-->0) {
n = in.nextInt (); m = in.nextInt ();
connect = new ArrayList [n];
color = new int [n];
for (i = 0; i < n; i++) connect [i] = new ArrayList <Integer> ();
for (i = 0; i < m; i++) {
a = in.nextInt () - 1; b = in.nextInt () - 1;
connect [a].add (b);
connect [b].add (a);
}
out.printf ("Scenario #%d:\n", ++j);
boolean ok = true;
for (i = 0; i < n; i++)
if (color [i] == 0 && !clr (i, 1)) {
ok = false; break;
}
if (!ok) out.println ("Suspicious bugs found!");
else out.println ("No suspicious bugs found!");
}
}
private static boolean clr (int node, int c) {
if (color [node] != 0) return color [node] == c;
int nc = (c == 1 ? 2 : 1);
color [node] = c;
for (int p : connect [node])
if (!clr (p, nc))
return false;
return true;
}
}
/** Faster input **/
class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader(){
din=new DataInputStream(System.in);
buffer=new byte[BUFFER_SIZE];
bufferPointer=bytesRead=0;
}
public Reader(String file_name) throws IOException{
din=new DataInputStream(new FileInputStream(file_name));
buffer=new byte[BUFFER_SIZE];
bufferPointer=bytesRead=0;
}
public String readLine() throws IOException{
byte[] buf=new byte[64]; // line length
int cnt=0,c;
while((c=read())!=-1){
if(c=='\n')break;
buf[cnt++]=(byte)c;
}
return new String(buf,0,cnt);
}
public int nextInt() throws IOException{
int ret=0;byte c=read();
while(c<=' ')c=read();
boolean neg=(c=='-');
if(neg)c=read();
do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');
if(neg)return -ret;
return ret;
}
public long nextLong() throws IOException{
long ret=0;byte c=read();
while(c<=' ')c=read();
boolean neg=(c=='-');
if(neg)c=read();
do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');
if(neg)return -ret;
return ret;
}
public double nextDouble() throws IOException{
double ret=0,div=1;byte c=read();
while(c<=' ')c=read();
boolean neg=(c=='-');
if(neg)c = read();
do {ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');
if(c=='.')while((c=read())>='0'&&c<='9')
ret+=(c-'0')/(div*=10);
if(neg)return -ret;
return ret;
}
private void fillBuffer() throws IOException{
bytesRead=din.read(buffer,bufferPointer=0,BUFFER_SIZE);
if(bytesRead==-1)buffer[0]=-1;
}
private byte read() throws IOException{
if(bufferPointer==bytesRead)fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException{
if(din==null) return;
din.close();
}
}Input
3 3
1 2
2 3
1 3
4 2
1 2
3 4
Output
Suspicious bugs found!
Scenario #2:
No suspicious bugs found!
Demonstration
SPOJ Solution-A Bug’s Life-Solution in C, C++, Java, Python