UVA 10319 - Manhattan ( 2SAT, SCC )

 UVA 10319 - Manhattan ( 2SAT, SCC )
/// Is there is a way to assign direction of all rows
/// and Column such that there will be a way to reach
/// from every (a,b) to (c,d)?

/// Idea: for each location to reach from (a,b) to (c,d)
/// either we have to go from dir of (a&d) or (b&c), which
/// is further reducible to (a|b) & (a&c) & (d|b) & (d&c)


///==================================================///
///                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     2002
#define inf    2000000010
#define MD     1000000007
#define eps    1e-9
///===============================///

vector<int>G[MX+2];
vector<int>FG[MX+2];
int n,tmm=0,St[MX+2],low[MX+2];
int Cp[MX+2],cm,Stk[MX+2],tp;

void Tarjan(int u) {
    St[u]=low[u]=++tmm;
    Stk[tp++]=u;
    for(int i=0; i<SZ(G[u]); i++) {
        int v=G[u][i];
        if(!St[v]) {
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        } else if(!Cp[v]) {
            low[u]=min(low[u],St[v]);
        }
    }
    if(St[u]==low[u]) {
        ++cm;
        while(true) {
            int xx=Stk[--tp];
            Cp[ xx ]=cm;/// Comp of xx is cm
            if( xx==u )break;
        }
    }
}

void Find_SCC( ) {
    CLR(St);
    CLR(Cp);
    cm=tmm=tp=0;///tot comp,dfs time & stk ptr
    for(int i=0; i<n; i++) {
        if(!St[i])Tarjan(i);
    }
}

void AddOR(int x,int y){
    G[ x^1 ].pb( y );
    G[ y^1 ].pb( x );
}

int main(){
    int tc,cs=1,i,j,k,m,r,c;
   // freopen("Out.txt","w",stdout);
    S(tc);
    while( tc-- ){

        S2(r,c);
        S(m);

        int lim=(r+c);

        n=lim+lim; ///total nodes:(True+False)

        for(i=0;i<=n;i++)G[ i ].clear();

        while(m--) {
            int r1,r2,c1,c2;

            S2(r1,c1);
            S2(r2,c2);
            r1--,r2--,c1--,c2--;

            r1*=2,r2*=2;
            c1*=2,c2*=2;
            c1+=2*r,c2+=2*r;
            /// 2*x: True & 2*x+1: False;

            if( r2<r1 ) c1^=1,c2^=1;
            if( c2<c1 ) r1^=1,r2^=1;

            if( r1==r2 && c1==c2 )continue;
            if( r1==r2 ) {
                G[ r1^1 ].pb( r2 );
                continue;
            }
            if( c1==c2 ) {
                G[ c1^1 ].pb( c2 );
                continue;
            }
            ///condition is : ( a & d ) || ( b & c )
            ///Reducing: (a|b) & (a&c) & (d|b) & (d&c)
            AddOR( r1,c1 );
            AddOR( r1,r2 );
            AddOR( c2,c1 );
            AddOR( c2,r2 );
        }

        Find_SCC( );

        bool Ok=true;
        for(i=0;i<n;i+=2){
            if( Cp[i]==Cp[ i^1 ] ){
                Ok=false;
                break;
            }
        }
        if( Ok ) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}