BZOJ 1832 2-SAT
好吧刚刚学了2-SAT，就只有做水题练手啦（甚至不用反边拓扑序大水题）
上代码
#include<cstdio>
#include<iostream>
#include<stack>
#include<cstring>
using namespace std;
const int INF=500+5;
const int maxn=5*1000+5;
struct egde{
int to,next;
} e[maxn];
int G[INF],low[INF],dfn[INF],cnt,be[INF],dfs_clock,be_cnt;
int n,m,id[INF][2],id_clock;
stack <int> S;
bool instack[INF];
void add(int x,int y){
if(x==y) return ;
// printf("%d %d\n",x,y);
e[++cnt].to=y;
e[cnt].next=G[x];
G[x]=cnt;
}
void clean(){
memset(G,0,sizeof(G));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(be,0,sizeof(be));
cnt=0;
dfs_clock=0;
be_cnt=0;
id_clock=0;
}
void tarjan(int x){
low[x]=dfn[x]=++dfs_clock;
instack[x]=true;
S.push(x);
for(int i=G[x];i;i=e[i].next){
int v=e[i].to;
if(!dfn[v]){
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if(instack[v]) low[x]=min(low[x],low[v]);
}
if(low[x]==dfn[x]){
int t;
be_cnt++;
do{
t=S.top();
S.pop();
be[t]=be_cnt;
instack[t]=false;
}while(t!=x);
}
}
bool check(){
for(int i=1;i<=n;++i)
if(be[id[i][0]]==be[id[i][1]]) return false;
return true;
}
int main(){
freopen("1832.in","r",stdin);
int k;
char s[2];
int orz[2],flag[2];
scanf("%d",&k);
while(k--){
clean();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) id[i][0]=++id_clock,id[i][1]=++id_clock;
for(int i=1;i<=m;++i){
for(int j=0;j<=1;++j){
scanf(" %c %d",&s[j],&orz[j]);
if(s[j]=='h') flag[j]=0;
else flag[j]=1;
}
add(id[orz[0]][flag[0]^1],id[orz[1]][flag[1]]);
add(id[orz[1]][flag[1]^1],id[orz[0]][flag[0]]);
}
for(int i=1;i<=id_clock;++i)
if(!dfn[i]) tarjan(i);
check()?printf("GOOD\n"):printf("BAD\n");
}
}