继续对2-sat建图的理解
下面的博客讲的挺好
http://hi.baidu.com/%8E%E1%D0%B3/blog/item/0a062c11ac76178e6538db55.html/cmtid/b2c6dddb2cd98c2211df9b50
#include<iostream> using namespace std; #define N 4100 typedef struct node* pointer; struct node { int ver; pointer next; }; struct rel { int s,t; }; rel dor[N],key[N]; pointer g[N]; int low[N],ord[N],cnt,scnt,stk[N],id[N]; bool instk[N]; int mymin(int a,int b) { if(a<b) return a; else return b; } void insert(int u,int v) { pointer ptr=new node; ptr->ver=v; ptr->next=g[u]; g[u]=ptr; } void tarjan(int e) { int t; pointer ptr; low[e]=++cnt; ord[e]=cnt; instk[e]=true; stk[++stk[0]]=e; ptr=g[e]; while(ptr!=NULL) { t=ptr->ver; if(!ord[t]) { tarjan(t); low[e]=mymin(low[e],low[t]); } if(instk[t]) low[e]=mymin(low[e],ord[t]); ptr=ptr->next; } if(ord[e]==low[e]) { scnt++; do { t=stk[stk[0]--]; instk[t]=false; id[t]=scnt; }while(t!=e); } return ; } void find_component(int n) { memset(ord,0,sizeof(ord)); memset(instk,0,sizeof(instk)); cnt=0,scnt=0,stk[0]=0; for(int i=1;i<=n;i++) if(!ord[i]) tarjan(i); return ; } int main() { int n,m,i,left,right,mid,a,b,ans; bool flag; while(scanf("%d%d",&n,&m)) { if(!n&&!m) break; for(i=1;i<=n;i++) { scanf("%d%d",&a,&b); key[i].s=++a,key[i].t=++b; } for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); dor[i].s=++a,dor[i].t=++b; } left=1,right=m,ans=0; while(left<=right) { mid=(left+right)/2; for(i=1;i<=4*n;i++) g[i]=NULL; for(i=1;i<=n;i++) { insert(key[i].s,key[i].t+2*n); insert(key[i].t,key[i].s+2*n); } for(i=1;i<=mid;i++) { insert(dor[i].s+2*n,dor[i].t); insert(dor[i].t+2*n,dor[i].s); } find_component(4*n); flag=true; for(i=1;i<=2*n;i++) if(id[i]==id[i+2*n]) { flag=false; break; } if(flag) { ans=mid; left=mid+1; } else right=mid-1; } printf("%d/n",ans); } return 0; }
