Hi Everyone,
I am trying to solve this problem. but getting TLE. Any suggestion for optimizing the code
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
/*========================================Templates=============================================*/
// datatypes
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
typedef float ft;
typedef unsigned int uint;
ull gcd( ull a, ull b ) { if( !b ) return a; return gcd( b, a % b ); }
#define tests(tc) int tc;scanf("%d",&tc);while(tc--)
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORN(i,a,b,n) for(int i=(a);i<=(b);i+=n)
#define FORR(i,a,b) for(int i=(a);i>=(b);--i)
#define FORRN(i,a,b,n) for(int i=(a);i>=(b);i-=n)
#define CLEAR(arr,v) memset(arr,v,sizeof(arr))
#define DB(x) cerr<<#x<<" : "<<x<<endl<<flush;
#define DB2(x,y) cerr<<#x<<" : "<<x<<" "<<#y<<" : "<<y<<endl<<flush;
#define DB3(x,y,z) cerr<<#x<<" : "<<x<<" "<<#y<<" : "<<y<<" "<<#z<<" : "<<z<<endl<<flush;
#define DB4(w,x,y,z) cerr<<#w<<" : "<<w<<" "<<#x<<" : "<<x<<" "<<#y<<" : "<<y<<" "<<#z<<" : "<<z<<endl<<flush;
#define DB5(v,w,x,y,z) cerr<<#v<<" : "<<v<<" "<<#w<<" : "<<w<<" "<<#x<<" : "<<x<<" "<<#y<< \
" : "<<y<<" "<<#z<<" : "<<z<<endl<<flush;
#define DBAR(arr,a,b) cerr<<#arr<<" : ";FOR(dbar,a,b) cerr<<arr[dbar]<<" ";cerr<<endl;
#define DBAR2(arr,a,b,x,y) cerr<<#arr<<endl;FOR(dbar,a,b){ FOR(dbar2,x,y)cerr<<arr[dbar][dbar2]<<" ";cerr<<endl;}
#define INF 1<<30
//#define DEBUG
/*======================================Templates Ends========================*/
/* Main Code Starts from here */
/*==================code for taking fast integer input========================*/
int sign;
int ch;
inline void S( int &x ) {
x=0;
while((ch<'0' || ch>'9') && ch!='-' && ch!=EOF) ch=getchar_unlocked();
if (ch=='-')
sign=-1 , ch=getchar_unlocked();
else
sign=1;
do
x = (x<<3) + (x<<1) + ch-'0';
while((ch=getchar_unlocked())>='0' && ch<='9');
x*=sign;
}
/*============================================================================*/
#define N 2002
int path[N][N];
int path_count[N];
bool color[N];
bool visited[N];
int n,m;
int a,b;
int save_i;
int kase;
/*
void clear() {
save_i = 1;
CLEAR(visited,0);
CLEAR(path_count,0);
CLEAR(path, 0);
CLEAR(color, 0);
}
*/
void clear() {
save_i = 1;
FOR(i,0,n) {
visited[i] = 0;
path_count[i] = 0;
color[i] = 0;
}
CLEAR(path, 0);
}
void get_input() {
//scanf("%d%d", &n, &m);
S(n);S(m);
clear();
FOR(i,1,m) {
//scanf("%d%d", &a, &b);
S(a);S(b);
path[a][path_count[a]++] = b;
path[b][path_count[b]++] = a;
}
}
bool dfs(int i){
stack<int> st;
st.push(i);
color[i] = 1;
visited[i] = true;
while(!st.empty()) {
int node = st.top();
st.pop();
//{DB(node)
//DBAR(path[node],0,path[node][path_count[node]-1])}
int childs = path_count[node]-1;
FOR(j, 0, childs) {
int cur_node = path[node][j];
if(visited[cur_node]) {
//cerr << "node " << path[node][j] << " already visited"<< endl;
//DB2(color[path[node][j]], color[node])
if(color[cur_node] == color[node])
return true;
}
else {
//cerr << "path " << path[node][j] << " added in stack"<< endl;
visited[cur_node] = true;
st.push(cur_node);
color[cur_node] = color[node]^1;
}
}
}
return false;
}
int notVisited() {
FOR(i,save_i,n){
if(!visited[i]) {
save_i = i;
return i;
}
}
return 0;
}
void solve(int kase) {
int i;
bool even_loop;
while(i=notVisited()) {
// { DB(i) }
even_loop = dfs(i);
if(even_loop) break;
}
printf("Scenario #%d:\n", kase);
if(even_loop) printf("Suspicious bugs found!\n");
else printf("No suspicious bugs found!\n");
}
int main (int argc, char const* argv[])
{
tests(tc) {
get_input();
solve(++kase);
}
return 0;
}