POJ 2723 Get Luffy Out （二分 + 2-SAT判定）
#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int VM=4200;const int EM=10010;struct Edge{ int to,nxt;}edge[EM<<1];int n,m,cnt,dep,top,atype,head[VM]; //atype 强连通分量的个数int dfn[VM],low[VM],vis[VM],belong[VM],x[VM],y[VM];int stack[VM],hash[VM];void Init(){ cnt=0, atype=0, dep=0, top=0; memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(belong,0,sizeof(belong));}void addedge(int cu,int cv){ edge[cnt].to=cv; edge[cnt].nxt=head[cu]; head[cu]=cnt++;}void Tarjan(int u){ dfn[u]=low[u]=++dep; stack[top++]=u; vis[u]=1; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(!dfn[v]){ Tarjan(v); low[u]=min(low[u],low[v]); }else if(vis[v]) low[u]=min(low[u],dfn[v]); } int j; if(dfn[u]==low[u]){ atype++; do{ j=stack[--top]; belong[j]=atype; vis[j]=0; }while(u!=j); }}int solve(int mid){ Init(); for(int i=0;i<mid;i++){ addedge(x[i],hash[y[i]]); addedge(y[i],hash[x[i]]); } for(int i=0;i<2*n;i++) if(!dfn[i]) Tarjan(i); for(int i=0;i<n;i++) if(belong[i]==belong[hash[i]]) return 0; return 1;}int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d%d",&n,&m)){ if(n==0 && m==0) break; int u,v; for(int i=0;i<n;i++){ scanf("%d%d",&u,&v); hash[u]=v; hash[v]=u; //标记配对的两个元素 } for(int i=0;i<m;i++) scanf("%d%d",&x[i],&y[i]); int l=0,r=m,mid,ans=0; while(l<=r){ mid=(l+r)>>1; //这里的二分就是确定可以到达的层数 if(solve(mid)){ //而对于某个确定的层，则就可以用2-sat来解决了 l=mid+1; ans=mid; }else r=mid-1; } /*下面这个二分只须16ms。。。。 int l=0,r=m+1,mid; while(l<r-1){ mid=(l+r)>>1; if(solve(mid)) l=mid; else r=mid; } */ printf("%d\n",ans); } return 0;}?