Try wid BFS.. thats the only alternative i can think off!! I got acc wid that!!
On Dec 6, 12:29 pm, "varma C.S.P" <verma....@gmail.com> wrote: > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
