首页 > 代码库 > HDU 3062
HDU 3062
http://acm.hdu.edu.cn/showproblem.php?pid=3062
2sat判定性问题模板
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <queue> #include <map> using namespace std ; struct node { int s,t,nxt ; }e[4000005] ; int n,m,idx,ans,tp,cnt,dfn[100005],vis[100005],low[100005],head[100005],st[100005],belong[100005] ; void add(int s,int t) { e[cnt].s=s ; e[cnt].t=t ; e[cnt].nxt=head[s] ; head[s]=cnt++ ; } void tarjan(int u) { dfn[u]=low[u]=++idx ; vis[u]=1 ; st[++tp]=u ; int v ; for(int i=head[u] ;i!=-1 ;i=e[i].nxt) { v=e[i].t ; if(!dfn[v]) { tarjan(v) ; low[u]=min(low[u],low[v]) ; } else if(vis[v]) low[u]=min(low[u],dfn[v]) ; } if(dfn[u]==low[u]) { ans++ ; while(1) { v=st[tp--] ; vis[v]=0 ; belong[v]=ans ; if(v==u)break ; } } } bool _2sat() { memset(vis,0,sizeof(vis)) ; memset(dfn,0,sizeof(dfn)) ; idx=tp=ans=0 ; for(int i=0 ;i<2*n ;i++) if(!dfn[i]) tarjan(i) ; for(int i=0 ;i<n ;i++) if(belong[2*i]==belong[(2*i)^1]) return false ; return true ; } int main() { while(~scanf("%d%d",&n,&m)) { cnt=0 ; memset(head,-1,sizeof(head)) ; while(m--) { int a,b,c,d ; scanf("%d%d%d%d",&a,&b,&c,&d) ; int u,v ; u=a*2+c ;v=b*2+d ; add(u,v^1) ;add(v,u^1) ; } if(_2sat())puts("YES") ; else puts("NO") ; } return 0 ; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。