POJ3207+tarjan+2-sat

  1 /*
  2 2-sat
  3 题意：给定一个圆，圆上一些点。两点一线。现给出一些线，这些线可以在圆内连起来，也可以在圆外。
  4     问有没有可能所有的线画完 且 不出现相交。
  5 思路：把线画在圆内或圆外 看成一个组合。其它的则建边。
  6 */
  7 #include<stdio.h>
  8 #include<string.h>
  9 #include<stdlib.h>
 10 #include<math.h>
 11 #include<algorithm>
 12 #include<iostream>
 13 #include<set>
 14 #include<stack>
 15 #include<queue>
 16 #include<map>
 17 #include<vector>
 18 using namespace std;
 19 
 20 typedef long long int64;
 21 //typedef __int64 int64;
 22 typedef pair<int64,int64> PII;
 23 #define MP(a,b) make_pair((a),(b)) 
 24 const int maxn = 2225;
 25 const int maxm = 250000;
 26 const int inf = 0x7fffffff;
 27 const double pi=acos(-1.0);
 28 const double eps = 1e-8;
 29 
 30 struct Edge{
 31     int u,v,next;
 32 }edge[ maxm*2+5 ];
 33 int cnt,head[ maxn ];
 34 int vis[ maxn ];
 35 int dfn[ maxn ],low[ maxn ];
 36 int belong[ maxn ],Cnt,id;
 37 stack<int>s;
 38 struct EDGE{
 39     int l,r;
 40 }E[ maxn ];
 41 
 42 void init(){
 43     id = Cnt = 0;
 44     cnt = 0;
 45     while( !s.empty() )
 46         s.pop();
 47     memset( head,-1,sizeof( head ) );
 48     memset( vis,-1,sizeof( vis ) );
 49     memset( dfn,-1,sizeof( dfn ) );
 50     memset( low,-1,sizeof( low ) );
 51 }
 52 
 53 void addedge( int a,int b ){
 54     edge[ cnt ].u = a;
 55     edge[ cnt ].v = b;
 56     edge[ cnt ].next = head[ a ];
 57     head[ a ] = cnt++;
 58 }
 59 
 60 bool ok( int L,int R ){
 61     int x1 = E[L].l;
 62     int y1 = E[L].r;
 63     int x2 = E[R].l;
 64     int y2 = E[R].r;
 65     if( x2>x1&&x2<y1 ){
 66         if( y2>=y1 ) return true;
 67         if( y2<=x1 ) return true;
 68     }
 69     if( y2>x1&&y2<y1 ){
 70         if( x2>=y1 ) return true;
 71         if( x2<=x1 ) return true;
 72     }
 73     return false;
 74 }
 75 
 76 void tarjan( int cur ){
 77     dfn[ cur ] = low[ cur ] = id++;
 78     vis[ cur ] = 1;
 79     s.push( cur );
 80     for( int i=head[ cur ];i!=-1;i=edge[i].next ){
 81         int nxt = edge[ i ].v;
 82         if( dfn[ nxt ]==-1 ){
 83             tarjan( nxt );
 84             low[ cur ] = min( low[ cur ],low[ nxt ] );
 85         }
 86         else if( vis[ nxt ]==1 ){
 87             low[ cur ] = min( low[ cur ],dfn[ nxt ] );
 88         }
 89     }
 90     if( dfn[ cur ]==low[ cur ] ){
 91         Cnt ++;
 92         while( 1 ){
 93             int tmp = s.top();
 94             s.pop();
 95             vis[ tmp ] = 0;
 96             belong[ tmp ] = Cnt;
 97             if( tmp==cur ) break;
 98         }
 99     }
100 }
101 
102 int main(){
103     int n,m;
104     while( scanf("%d%d",&n,&m)==2 ){
105         init();
106         int a,b;
107         for( int i=1;i<=m;i++ ){
108             scanf("%d%d",&a,&b);
109             a++,b++;
110             E[ i ].l = min( a,b );
111             E[ i ].r = max( a,b );
112         }
113         for( int i=1;i<=m;i++ ){
114             for( int j=i+1;j<=m;j++ ){
115                 if( ok( i,j )==true ){
116                     addedge( i,j+m );
117                     addedge( j+m,i );
118                     addedge( i+m,j );
119                     addedge( j,i+m );
120                 }
121             }
122         }//build mat
123         for( int i=1;i<=2*m;i++ ){
124             if( dfn[i]==-1 ){
125                 tarjan( i );
126             }
127         }
128         //
129         bool f = true;
130         for( int i=1;i<=m;i++ ){
131             if( belong[i]==belong[i+m] ){
132                 f = false;
133                 break;
134             }
135         }
136         if( f==false ) printf("the evil panda is lying again");
137         else printf("panda is telling the truth...");
138         printf("
");
139     }
140     return 0;
141 }
View Code
keep moving...