POJ1291 This Sentence is False
題名は問題名なのであしからず。
2-SATに見えて考えてたらわけがわからなくなり考え直したら無向グラフだったことが判明。
思い切りunion-findが役立つ。UFかわいいよUF。
#include<stdio.h> #include<algorithm> #include<vector> #include<math.h> #include<string> #include<iostream> #include<stdlib.h> using namespace std; #define LIMIT 2000 int par[LIMIT]; int ran[LIMIT]; int ren[LIMIT]; int renp[LIMIT]; void init() { for(int i=0;i<LIMIT;i++) { par[i]=i; ran[i]=0; ren[i]=1; if(i%2==0) { renp[i]=1; } else { renp[i]=-1; } } } int find(int a) { if(par[a]==a) { return a; } else { return par[a]=find(par[a]); } } void unite(int a,int b) { a=find(a); b=find(b); if(a==b) { return; } if(ran[a]>ran[b]) { par[b]=a; ren[a]+=ren[b]; renp[a]+=renp[b]; } else { par[a]=b; ren[b]+=ren[a]; renp[b]+=renp[a]; } if(ran[a]==ran[b]) { ran[b]++; } } int main() { for(;;) { int num; scanf("%d",&num); if(num==0) { break; } init(); for(int i=0;i<num;i++) { char gomi[20]; int zan; char dat[10]; scanf("%s%d%s%s",gomi,&zan,gomi,dat); zan--; if(dat[0]=='t') { unite(i*2,zan*2); unite(i*2+1,zan*2+1); } else { unite(i*2,zan*2+1); unite(i*2+1,zan*2); } } int han=0; for(int i=0;i<num;i++) { if(find(i*2)==find(i*2+1)) { han=1; } } if(han==1) { printf("Inconsistent\n"); continue; } int ret=0; for(int i=0;i<num*2;i++) { if(find(i)==i) { ret+=max(ren[i]+renp[i],ren[i]-renp[i]); } } printf("%d\n",ret/4); } }