hdu 3062 2-sat

#include<stdio.h>
#include<string.h>
#define N 2100
struct node {
int u,v,next;
}bian[N*N];
int min(int a,int b) {
return a>b?b:a;
}
int yong,dfn[N],low[N],ans[N],stac[N],top,index,num,head[N],visit[N];
void addedge(int u,int v) {
bian[yong].u=u;
bian[yong].v=v;
bian[yong].next=head[u];
head[u]=yong++;
}
void tarjan(int u) {
dfn[u]=low[u]=++index;
stac[++top]=u;
visit[u]=1;
int i;
for(i=head[u];i!=-1;i=bian[i].next) {
int v=bian[i].v ;
if(!dfn[v]) {
tarjan(v);
low[u]=min(low[u],low[v]);
}
else
if(visit[v]==1)
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]) {
++num;
int t;
do{
t=stac[top--];
ans[t]=num;
 visit[t]=2;
}while(t!=u);
}


}
int main(){
int n,m,i,j,ii,jj,a,b,c,d;
while(scanf("%d%d",&n,&m)!=EOF) {
yong=0;index=0;num=0;top=0;//初始化
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(head,-1,sizeof(head));
memset(stac,0,sizeof(stac));
memset(ans,0,sizeof(ans));
memset(visit,0,sizeof(visit));
while(m--) {
scanf("%d%d%d%d",&a,&b,&c,&d);
i=a*2+c;
j=b*2+d;
if(c==0)
ii=i+1;
else
ii=i-1;
if(d==0)
jj=j+1;
else
jj=j-1;
             addedge(i,jj);
addedge(j,ii);
}
for(i=0;i<2*n-1;i++)
if(visit[i]!=2)
tarjan(i);
for(i=0;i<n;i++)
if(ans[i*2]==ans[i*2+1])
break;
if(i==n)
printf("YES ");
else
printf("NO ");
}
return 0;
}
原文地址:https://www.cnblogs.com/thefirstfeeling/p/4410855.html