Augury @ 2023-01-31 10:25:40
码风奇怪,请不要嫌弃
#include<bits/stdc++.h>
#define f(x) (x=='h')
using namespace std;
const int maxn=210;
int n,m;
int dfn[maxn],low[maxn],col[maxn];
bool vis[maxn];
stack<int>st;
int cnt=0,clr=0;
vector<int>g[maxn];
void tarjan(int now){
dfn[now]=low[now]=++cnt;
vis[now]=1;
st.push(now);
for(int i=0;i<(int)g[now].size();i++){
int nxt=g[now][i];
if(!dfn[nxt]){
tarjan(nxt);
low[now]=min(low[now],low[nxt]);
}
else if(vis[nxt])low[now]=min(low[now],dfn[nxt]);
}
if(dfn[now]==low[now]){
clr++;
int tmp=-1;
while(tmp!=now){
tmp=st.top();
st.pop();
col[tmp]=clr;
vis[tmp]=1;
}
}
}
void init(){
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(col,0,sizeof(col));
for(int i=1;i<=n<<1;i++)g[i].clear();
cnt=clr=0;
}
void real_main(){
scanf("%d%d",&n,&m);
init();
for(int i=1;i<=m;i++){
char a,c;
int b,d;
cin>>a>>b>>c>>d;
g[b+(!f(a))*n].push_back(d+f(c)*n);
g[d+(!f(c))*n].push_back(b+f(a)*n);
}
for(int i=1;i<=n<<1;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++){
if(col[i]==col[i+n]){
cout<<"BAD\n";
return;
}
}
cout<<"GOOD\n";
return;
}
int main(){
int K;
scanf("%d",&K);
while(K--)real_main();
}
再上面的 tarjan
中,节点出栈后应该将 vis[now]=0
,然鹅蒟蒻写成了 vis[now]=1
,