陰陽さん @ 2021-03-26 21:07:48
#include<bits/stdc++.h>
using namespace std;
int m,n,tot=0,T;
int v[200010],q[200010];//,jie[10010],ud[10010];
vector<int>p[200010],fp[200010];
int exx(int x){
if(x<=n)return x+n;
return x-n;
}
void ex(int x,int a,int y,int b){
int w=x,z=y;
if(a)x+=n;else w+=n;
if(b)y+=n;else z+=n;
p[w].push_back(y);
p[z].push_back(x);
fp[y].push_back(w);
fp[x].push_back(z);
}
void dfs1(int x){
v[x]=1;
int i,j,k,l=fp[x].size();
for(i=0;i<l;i++){
k=fp[x][i];
if(!v[k])dfs1(k);
}
q[++tot]=x;
}
int dfs2(int x,int y){
v[x]=0;
if(x==y)return 1;
int i,j,k,l=p[x].size();
for(i=0;i<l;i++){
k=p[x][i];
if(v[k])
if(dfs2(k,y))return 1;
}
return 0;
}
int main(){
cin>>T;
while(T--){
cin>>n>>m;
int i,j,k,fl=0,x,y,a,b;tot=0;
memset(v,0,sizeof v);
memset(q,0,sizeof q);
for(i=0;i<=n;i++)p[i].clear(),fp[i].clear();
string s1,s2;
while(m--){
cin>>s1>>s2;
if(s1[0]=='m')a=0;else a=1;
if(s2[0]=='m')b=0;else b=1;
x=0;for(i=1;i<s1.size();i++)x=x*10+s1[i]-'0';
y=0;for(i=1;i<s2.size();i++)y=y*10+s2[i]-'0';
// printf("(%d %d %d %d)\n",x,a,y,b);
ex(x,a,y,b);
}
for(i=1;i<=n*2;i++){
if(!v[i])dfs1(i);
}
while(tot){
if(v[q[tot]])
if(dfs2(q[tot],exx(q[tot]))){
cout<<"BAD"<<endl,fl=1;break;
}
tot--;
}
if(!fl){
cout<<"GOOD"<<endl;
}
}
return 0;
}
by 陰陽さん @ 2021-04-18 21:04:54
劳资AC了哈哈哈哈