本文共 1628 字，大约阅读时间需要 5 分钟。
2-SAT 问题 关键在于处理关系 看了别人的解析 自己还是不行呀
代码：
#include #include #include #include #include #include #include #include #include #define LL long longusing namespace std;const int N=2005;struct node{ struct tt *next;}mem[N];struct tt{ int j; struct tt *next;};int dfn[N];int low[N];bool in[N];bool visited[N];int deep;int f[N];stack str;void build(int i,int j){ struct tt *t=new tt; t->j=j; t->next=mem[i].next; mem[i].next=t;}void Dele(int n){ for(int i=0;i<=n;++i) mem[i].next=NULL;}void Tarjan(int x){ visited[x]=true; str.push(x); in[x]=true; dfn[x]=low[x]=deep++; struct tt *t=mem[x].next; while(t!=NULL) { if(visited[t->j]==false) { Tarjan(t->j); low[x]=min(low[x],low[t->j]); }else if(in[t->j]==true) { low[x]=min(low[x],dfn[t->j]); } t=t->next; } if(low[x]==dfn[x]) { while(str.top()!=x) { int k=str.top(); str.pop(); in[k]=false; f[k]=x; } int k=str.top(); str.pop(); in[k]=false; f[k]=x; }}inline void Judge(int a,int b,int c,char s[],int n){ if(s[0]=='A') { if(c==1) { build(a+n,a);build(b+n,b);//a表示1 a+n表示0 b也一样 }else { build(a,b+n);build(b,a+n); } return ; } if(s[0]=='O') { if(c==1) { build(a+n,b);build(b+n,a); }else { build(a,a+n);build(b,b+n); } return ; } if(s[0]=='X') { if(c==1) { build(a,b+n);build(a+n,b); build(b,a+n);build(b+n,a); }else { build(a,b);build(a+n,b+n); build(b,a);build(b+n,a+n); } }}int main(){ //freopen("data.txt","r",stdin); int n,m; while(scanf("%d %d",&n,&m)!=EOF) { int a,b,c; char s[5]; for(int i=0;i
转载于:https://www.cnblogs.com/liulangye/archive/2012/08/15/2639724.html