/*
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;
}
分享到:
相关推荐
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ水题集-----50道左右-----增加自信啊..
北大POJ3292-Semi-prime H-numbers 解题报告+AC代码
非常全的poj答案库 1164-1874 1000-4007
poj 800+ 题目源代码,多年做题积累 包含各种类型经典题目
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ2002-Squares 解题报告+AC代码
北大POJ2305-Basic remains POJ2305-Basic remains
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
北大POJ1321-Chess Problem POJ1321-Chess Problem
用Java代码实现POJ(PKU)上题2494!
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
POJ2942-Knights of the ...【Tarjan算法】 解题报告+AC代码 http://hi.csdn.net/!s/F3L8HO ================================== 我的POJ所有解题报告:http://blog.csdn.net/lyy289065406/article/details/6642573
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
poj经典数据结构题目解题报告poj经典数据结构题目解题报告
分治+中位数第 9 题:poj1723 SOLDIERSN soldiers of the land Gridland are randomly scatter
很有用的解题报告。。是acm初级提高的必备资料。。。。。
北大POJ3273-Monthly Expense POJ3273-Monthly Expense
北大POJ初级-简单搜索 解题报告+AC代码