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\n");

else

printf("NO\n");

}

return 0;

}

巴特西

hdu 3062 2-sat

最新文章

热门文章