【模板】 2-sat

  1 //https://blog.csdn.net/jarjingx/article/details/8521690
  2 //上面是讲解，下面是代码
  3 //https://www.e-learn.cn/content/qita/1061337
  4 //poj3648
  5 //女2n男2n+1
  6 #include<iostream>
  7 #include<cstdio>
  8 #include<cstring>
  9 #include<queue>
 10 using namespace std;
 11 const int N=1e5+6;
 12 struct edge{
 13     int to,nex;
 14 }e[N];
 15 edge e2[N];
 16 int h[N],h2[N],sta[N],col[N],blg[N],low[N],dfn[N],in[N],ops[N];
 17 bool insta[N];
 18 int n,m,cnt,cnt2,dfsnum,top;
 19 void add(int a,int b){
 20     e[++cnt]=(edge){b,h[a]};
 21     h[a]=cnt;
 22 }
 23 void add2(int a,int b){
 24     e2[++cnt2]=(edge){b,h2[a]};
 25     h2[a]=cnt2;
 26 }
 27 void tarjan(int x){
 28     low[x]=dfn[x]=++dfsnum;
 29     insta[x]=1;
 30     sta[++top]=x;
 31     for(int i=h[x];i;i=e[i].nex){
 32         int v=e[i].to;
 33         if(!dfn[v]){
 34             tarjan(v);
 35             low[x]=min(low[x],low[v]);
 36         }
 37         else if(insta[v]) low[x]=min(low[x],dfn[v]);
 38     }
 39     int cur;
 40     if(dfn[x]==low[x]){
 41         ++blg[0];
 42         do{
 43             cur=sta[top--];
 44             insta[cur]=0;
 45             blg[cur]=blg[0];
 46         }while(cur!=x);
 47     }
 48 }
 49 int main(){
 50     while(~scanf("%d%d",&n,&m)){
 51         //读入建图
 52         cnt=1;dfsnum=0;top=0,cnt2=1;
 53         memset(col,0,sizeof(col));
 54         memset(h,0,sizeof(h));
 55         memset(h2,0,sizeof(h2));
 56         memset(insta,0,sizeof(insta));
 57         memset(dfn,0,sizeof(dfn));
 58         memset(in,0,sizeof(in));
 59         if(n==0 && m==0) break;
 60         for(int i=1;i<=m;++i){
 61             int a,b;char c,d;
 62             scanf("%d%c %d%c",&a,&c,&b,&d);
 63             if(c==‘h‘ && d==‘h‘){
 64                 add(2*a+1,2*b);
 65                 add(2*b+1,2*a);
 66             }
 67             if(c==‘h‘ && d==‘w‘){
 68                 add(2*a+1,2*b+1);
 69                 add(2*b,2*a);
 70             }
 71             if(c==‘w‘ && d==‘h‘){
 72                 add(2*a,2*b);
 73                 add(2*b+1,2*a+1);
 74             }
 75             if(c==‘w‘ && d==‘w‘){
 76                 add(2*a,2*b+1);
 77                 add(2*b,2*a+1);
 78             }
 79         }
 80         add(0,1);
 81         //缩点
 82         for(int i=0; i < 2*n; ++i){
 83             if(!dfn[i]) tarjan(i);
 84         }
 85         bool fg=1;
 86         for(int i=0;i<2*n;i+=2){
 87             if(blg[i]==blg[i^1]){
 88                 puts("bad luck");
 89                 fg=0;
 90                 break;
 91             }
 92         }
 93         if(!fg) continue;
 94         //建反向图
 95         for(int u=0;u<2*n;++u){
 96             for(int i=h[u];i;i=e[i].nex){
 97                 int v=e[i].to;
 98                 int t1=blg[u],t2=blg[v];
 99                 if(t1!=t2){
100                     add2(t2,t1);
101                     ++in[t1];
102                 }
103             }
104         }
105         for(int i=0;i<2*n;i+=2){
106             ops[blg[i]]=blg[i^1];
107             ops[blg[i^1]]=blg[i];
108         }
109         //拓扑(染色)
110         queue<int> q;
111         for(int i=1;i<=blg[0];++i){
112             if(!in[i]) q.push(i);
113         }
114         while(!q.empty()){
115             int u=q.front();
116             q.pop();
117             if(!col[u]){
118                 col[u]=1;
119                 col[ops[u]]=-1;
120             }
121             for(int i=h2[u];i;i=e2[i].nex){
122                 int v=e2[i].to;
123                 --in[v];
124                 if(!in[v]) q.push(v);
125             }
126         }
127         //输出
128         for(int i=1;i<n; ++i){
129             if(col[blg[i<<1]]==-1) printf("%dw",i);
130             else printf("%dh",i);
131             if(i<n-1) printf(" ");
132             else printf("\n");
133         }
134     }
135     return 0;
136 }