SPOJ BUGLIFE (2SAT Basic/Bipartite Checking)

SPOJ BUGLIFE (2SAT Basic/Bipartite Checking)

///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;

///  Digit     0123456789012345678 ///
#define MX     4005
#define inf    2000000010
#define MD     1000000007
#define eps    1e-9
///===============================///

vector<int>G[MX+2],Rg[MX+2],rv;
int cm,Cp[MX+2];
bool vis[MX+2];

void Dfs(int u) {
    if( vis[ u ])return;
    vis[ u ]=1;
    for(int i=0; i<SZ(G[u]); i++) {
        Dfs( G[u][i] );
    }
    rv.pb( u );
}

void DfsR(int u) {
    if( vis[ u ])return;
    vis[ u ]=1;
    for(int i=0; i<SZ(Rg[u]); i++) {
        DfsR( Rg[u][i] );
    }
    Cp[ u ]=cm;
}

int main() {
    int n,m,tc,cs=1,i,j,k,x,y;
    S(tc);
    while(tc--) {
        S2(n,m);
        for(i=1; i<=n+n; i++)G[i].clear(),Rg[i].clear();
        for(i=1;i<=m;i++){
            S2(x,y);
            ///Fst male OR Second is male;
            G[ n+x ].pb( y );
            G[ n+y ].pb( x );
            ///Fst female OR Second is female;
            G[ x ].pb( y+n );
            G[ y ].pb( x+n );
            ///Reverse Graph for Kosaraju
            Rg[ y ].pb( n+x );
            Rg[ x ].pb( n+y );
            Rg[ y+n ].pb( x );
            Rg[ x+n ].pb( y );
        }
        CLR(vis);
        rv.clear();
        for(i=1; i<=n+n; i++) {
            if(!vis[i]) {
                Dfs(i);
            }
        }
        CLR(vis);
        cm=0;
        int sz=rv.size();
        for(i=sz-1; i>=0; i--) {
            if(!vis[ rv[i] ]) {
                ++cm;
                DfsR( rv[i] );
            }
        }
        bool f=1;
        for(i=1;i<=n;i++){
            if( Cp[i]==Cp[n+i] ){
                f=0;
                break;
            }
        }
        printf("Scenario #%d:\n",cs++);
        if(!f) printf("Suspicious bugs found!\n");
        else printf("No suspicious bugs found!\n");
    }
    return 0;
}