Backjoon Online Judge no.2207 가위바위보 September 30, 2013

#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;
int N,V;
vector<vector<int> > v,G,scc;
vector<int> tmp1,tmp2;
vector<bool> vis,vis2;
int RetIndex(int a) {
    return a>0?((a-1)*2):((a+1)*-2+1);
}
void go(int now) {
    vis[now] = true;
    for ( int i = 0 ; i < v[now].size() ; i++ )
        if ( !vis[v[now][i]] )
            go(v[now][i]);
    tmp1.push_back(now);
}
bool ok(int now) {
    int prev = now&1?(now-1):(now+1);
    if ( vis2[prev] ) return false;
    vis[now] = vis2[now] = true;
    for ( int i = 0; i < G[now].size() ; i++ )
        if ( !vis[G[now][i]] )
            if ( !ok(G[now][i]) )
                return false;
    return true;
}
int main() {
    scanf("%d %d",&N,&V);
    V *= 2;
    v.resize(V+1),G.resize(V+1),scc.resize(V+1);
    for ( int i = 0 ; i < N ; i++ ) {
        int a,b;
        scanf("%d%d",&a,&b);
        int A,B,minusA,minusB;
        A = RetIndex(a);
        minusA = RetIndex(-a);
        B = RetIndex(b);
        minusB = RetIndex(-b);
        v[minusA].push_back(B);
        v[minusB].push_back(A);
        G[B].push_back(minusA);
        G[A].push_back(minusB);
    }
    vis.resize(V,false);
    vis2.resize(V,false);
    for ( int i = 0 ; i < V ; i++ )
        if ( !vis[i] )
            go(i);
    fill(vis.begin(),vis.end(),false);
    for ( int i = (int)tmp1.size()-1 ; i >= 0 ; i-- )
        if ( !vis[i] ) {
            fill(vis2.begin(),vis2.end(),false);
            if ( !ok(tmp1[i]) )
                return printf("OTL\n"),0;
        }
    printf("^_^\n");
    return 0;
}