zcmimi's blog
avatar
zc
2020-10-05 16:10:20
  • 本文总阅读量

查看原题

点击跳转

#include<bits/stdc++.h>
using std::cin;
const int N=411;
int n,m,cnt,head[N];
struct edge{int to,nxt;}e[4011];
void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
int dfn[N],low[N],sz,st[N],tp,bl[N],tt;
bool v[N];
void cmin(int&x,int y){if(y<x)x=y;}
void tarjan(int x){
    dfn[x]=low[x]=++sz;st[++tp]=x;v[x]=1;
    for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
        if(!dfn[to])tarjan(to),cmin(low[x],low[to]);
        else if(v[to])cmin(low[x],dfn[to]);
    if(low[x]==dfn[x]){
        ++tt;
        while(int k=st[tp--]){
            bl[k]=tt;v[k]=0;
            if(k==x)break;
        }
    }
}
bool solve(){
    cnt=0,memset(head,0,sizeof head),memset(dfn,0,sizeof dfn),sz=tt=0;
    cin>>n>>m;
    int x,y;char cx,cy;
    for(int i=1;i<=m;++i)
        cin>>cx>>x>>cy>>y,
        add(x+n*(cx=='m'),y+n*(cy=='h')),
        add(y+n*(cy=='m'),x+n*(cx=='h'));
    for(int i=1;i<=n*2;++i)if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;++i)
        if(bl[i]==bl[i+n])return 0;
    return 1;
}
int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);
    int T;cin>>T;
    while(T--)puts(solve()?"GOOD":"BAD");
}
LG 4171 [JSOI2010]满汉全席
comment评论
Search
search