POJ3207+Tarjan+2-sat

/*
2-sat
題意：給定一個圓，圓上一些點。兩點一線。現給出一些線，這些線可以在圓內連起來，也可以在圓外。
	問有沒有可能所有的線畫完 且 不出現相交。
思路：把線畫在圓內或圓外 看成一個組合。其它的則建邊。
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<set>
#include<stack>
#include<queue>
#include<map>
#include<vector>
using namespace std;

typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b)) 
const int maxn = 2225;
const int maxm = 250000;
const int inf = 0x7fffffff;
const double pi=acos(-1.0);
const double eps = 1e-8;

struct Edge{
	int u,v,next;
}edge[ maxm*2+5 ];
int cnt,head[ maxn ];
int vis[ maxn ];
int dfn[ maxn ],low[ maxn ];
int belong[ maxn ],Cnt,id;
stack<int>s;
struct EDGE{
	int l,r;
}E[ maxn ];

void init(){
	id = Cnt = 0;
	cnt = 0;
	while( !s.empty() )
		s.pop();
	memset( head,-1,sizeof( head ) );
	memset( vis,-1,sizeof( vis ) );
	memset( dfn,-1,sizeof( dfn ) );
	memset( low,-1,sizeof( low ) );
}

void addedge( int a,int b ){
	edge[ cnt ].u = a;
	edge[ cnt ].v = b;
	edge[ cnt ].next = head[ a ];
	head[ a ] = cnt++;
}

bool ok( int L,int R ){
	int x1 = E[L].l;
	int y1 = E[L].r;
	int x2 = E[R].l;
	int y2 = E[R].r;
	if( x2>x1&&x2<y1 ){
		if( y2>=y1 ) return true;
		if( y2<=x1 ) return true;
	}
	if( y2>x1&&y2<y1 ){
		if( x2>=y1 ) return true;
		if( x2<=x1 ) return true;
	}
	return false;
}

void tarjan( int cur ){
	dfn[ cur ] = low[ cur ] = id++;
	vis[ cur ] = 1;
	s.push( cur );
	for( int i=head[ cur ];i!=-1;i=edge[i].next ){
		int nxt = edge[ i ].v;
		if( dfn[ nxt ]==-1 ){
			tarjan( nxt );
			low[ cur ] = min( low[ cur ],low[ nxt ] );
		}
		else if( vis[ nxt ]==1 ){
			low[ cur ] = min( low[ cur ],dfn[ nxt ] );
		}
	}
	if( dfn[ cur ]==low[ cur ] ){
		Cnt ++;
		while( 1 ){
			int tmp = s.top();
			s.pop();
			vis[ tmp ] = 0;
			belong[ tmp ] = Cnt;
			if( tmp==cur ) break;
		}
	}
}

int main(){
	int n,m;
	while( scanf("%d%d",&n,&m)==2 ){
		init();
		int a,b;
		for( int i=1;i<=m;i++ ){
			scanf("%d%d",&a,&b);
			a++,b++;
			E[ i ].l = min( a,b );
			E[ i ].r = max( a,b );
		}
		for( int i=1;i<=m;i++ ){
			for( int j=i+1;j<=m;j++ ){
				if( ok( i,j )==true ){
					addedge( i,j+m );
					addedge( j+m,i );
					addedge( i+m,j );
					addedge( j,i+m );
				}
			}
		}//build mat
		for( int i=1;i<=2*m;i++ ){
			if( dfn[i]==-1 ){
				tarjan( i );
			}
		}
		//
		bool f = true;
		for( int i=1;i<=m;i++ ){
			if( belong[i]==belong[i+m] ){
				f = false;
				break;
			}
		}
		if( f==false ) printf("the evil panda is lying again");
		else printf("panda is telling the truth...");
		printf("\n");
	}
	return 0;
}