NaCly_Fish @ 2019-02-10 21:23:07
莫名只有50分。。求找错
(应该不是清空数组的问题)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
#define inf 0x3f3f3f3f
#define ll long long
#define N 203
#define reg register
using namespace std;
vector<int> adj[N];
int low[N],dfn[N],clr[N],stk[N];
bool vis[N];
int scc,size,cnt;
inline void read(int &x);
void print(int x);
bool solve();
void tarjan(int u);
int main(){
int T;
bool ans;
read(T);
while(T--){
ans = solve();
printf(ans?"GOOD\n":"BAD\n");
}
return 0;
}
bool solve(){
string s1,s2;
cnt = scc = size = 0;
memset(clr,0,sizeof(clr));
memset(dfn,0,sizeof(clr));
memset(vis,0,sizeof(vis));
memset(low,0,sizeof(low));
memset(stk,0,sizeof(stk));
int n,m,a,b,va,vb;
read(n),read(m);
for(int i=1;i<=(n<<1);++i)
adj[i].clear();
for(int i=1;i<=m;++i){
cin>>s1>>s2;
a = s1[1]-'0';
va = s1[0]=='h'?1:0;
b = s2[1]-'0';
vb = s2[0]=='h'?1:0;
adj[a+n*(va&1)].push_back(b+n*(vb^1));
adj[b+n*(vb&1)].push_back(a+n*(va^1));
}
for(int i=1;i<=(n<<1);++i){
if(dfn[i]) continue;
tarjan(i);
}
for(int i=1;i<=n;++i){
if(clr[i]!=clr[i+n]) continue;
return false;
}
return true;
}
void tarjan(int u){
low[u] = dfn[u] = ++cnt;
vis[u] = true;
stk[++size] = u;
int v,l = adj[u].size();
for(int i=0;i<l;++i){
v = adj[u][i];
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u],low[v]);
}else if(vis[v])
low[u] = min(low[u],dfn[v]);
}
if(low[u]!=dfn[u]) return;
++scc;
do{
vis[stk[size]] = false;
clr[stk[size]] = scc;
--size;
}while(stk[size+1]!=u);
}
inline void read(int &x){
x = 0;
char c = getchar();
while(c<'0'||c>'9') c = getchar();
while(c>='0'&&c<='9'){
x = (x<<3)+(x<<1)+(c^48);
c = getchar();
}
}
void print(int x){
if(x>9) print(x/10);
putchar(x%10+'0');
}
by Catalan1906 @ 2019-02-10 21:24:57
去你的萌妹子,去你的刚学2-SAT,这个人怎么这么fAKe
by 林则徐左宗棠 @ 2019-02-10 21:27:48
先膜为敬Orz
by 小粉兔 @ 2019-02-10 21:28:07
「老 Faker 学了好久 OI 学到 2-SAT 写挂了」
是这个意思吧
by Sai0511 @ 2019-02-10 21:28:54
去你的萌妹子,去你的刚学2-SAT,这个人怎么这么fAKe
by NaCly_Fish @ 2019-02-10 21:29:59
@Neptune_Disaster 您ddw QAQ
by Catalan1906 @ 2019-02-10 21:33:26
@NaCly_Fish 这个人怎么这么fAKe,让蒟蒻OIer引起不适,建议封号!
您ddw, ddjxd, AKIOI.
by NaCly_Fish @ 2019-02-10 21:34:57
@Neptune_Disaster 不要哇
by 林则徐左宗棠 @ 2019-02-10 21:35:48
不要打架不要打架
by FP·荷兰猪 @ 2019-02-10 21:38:11
坐等memset0
by GoldenPotato137 @ 2019-02-10 21:38:31
@NaCly_Fish
fAKe差评
不会2SAT,告辞