I am getting a lot of tle's for this problem.
https://www.spoj.pl/problems/BUGLIFE/
Here is my code
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int g[2001][2001];
int color[2001];
short stack[5001];
int bugs, rel;
int inline complement(int n);
bool inline dfs();
int v1, v2;
int main()
{
int cases;
scanf("%d", &cases);
for(int i=1; i<=cases; i++)
{
scanf("%d %d", &bugs, &rel);
memset(g, 0x00, sizeof g);
int relq = rel;
while(relq--)
{
scanf("%d %d", &v1, &v2);
g[v1][++g[v1][0]]=v2;
g[v2][++g[v2][0]]=v1;
}
printf("Scenario #%d:\n", i);
if(dfs())
{
printf("No suspicious bugs found!\n");
}
else
{
printf("Suspicious bugs found!\n");
}
}
return 0;
}
int inline complement(int n)
{
if(n==1)
return 2;
if(n==2)
return 1;
}
bool inline dfs() //iterative DFS
{
int node, no, in;
memset(color, 0x00, (bugs+1)*sizeof(int));
stack[0]=0;
for(int it = 1; it<=bugs; it++)
{
if(color[(it)]==0 && g[(it)][0]!=0)
{
stack[++stack[0]]=(it);
color[(it)] = 1;
while(stack[0] && (rel>0)) //if stack is not empty
{
in = stack[stack[0]--];
no = g[in][0];
for(int j=1; j<=no; j++)
{
node = g[in][j];
if(color[node]!=0)
{
if(color[node] == color[in])
{
return false;
}
}
else
{
color[node] = complement(color[in]);
stack[++stack[0]]=node;
rel--;
}
}
}
}
}
return true;
}
Please help me.
Ashok
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
