JK_LOVER @ 2020-08-09 21:02:35
#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
int read(){
int x = 0,f = 0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return f?-x:x;
}
struct Edge{int to,nxt;}e[N<<1];
int head[N],cnt = 1,st[N],n,m,top = 0,col[N],dfn[N],low[N],tot = 0,tim = 0;
void Init(){
cnt = 1;tot = 0;top = 0;tim = 0;
memset(col,0,sizeof(col));
memset(dfn,0,sizeof(col));
memset(low,0,sizeof(low));
memset(st,0,sizeof(st));
}
void add(int x,int y){
e[++cnt].nxt = head[x];e[cnt].to = y;head[x] = cnt;
}
void tarjin(int x){
dfn[x] = low[x] = ++tim;st[++top] = x;
for(int i = head[x];i;i = e[i].nxt){
int y = e[i].to;
if(!dfn[y]){
tarjin(y);low[x] = min(low[x],low[y]);
}
else if(!col[y]) low[x] = min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
col[x] = ++tot;
while(st[top] != x){
col[st[top]] = tot;
top--;
}
top--;
}
}
int main(){
// ios::sync_with_stdio(0);
int K;cin>>K;
while(K--){
Init();
cin>>n>>m;
for(int i = 1;i <= m;i++){
char ch1[10],ch2[10];int a,b;
scanf("%s%s",ch1,ch2);
a = ch1[1] - '0';b = ch2[1] - '0';
if(ch1[0] == 'm' && ch2[0] == 'h')
{
add(a+n,b+n);add(b,a);
}
if(ch1[0] == 'h' && ch2[0] == 'h')
{
add(a,b+n);add(b,a+n);
}
if(ch1[0] == 'm' && ch2[0] == 'm')
{
add(a+n,b);add(b+n,a);
}
if(ch1[0] == 'h' && ch2[0] == 'h')
{
add(a,b+n);add(b,a+n);
}
}
for(int i = 1;i <= n*2;i++){
if(!dfn[i]) tarjin(i);
}
int a = 0;
for(int i = 1;i <= n;i++){
if(col[i] == col[i+n] && !a){
printf("BAD\n");a=1;
}
}
if(!a) printf("GOOD\n");
}
return 0;
}
by JK_LOVER @ 2020-08-09 21:04:51
本地AC，提交就是AC不了。
by JK_LOVER @ 2020-08-09 21:09:19
少了个 memset ，但还是 20 分。o((>ω< ))o
by JK_LOVER @ 2020-08-09 21:10:46
我知道了，后面的数字不止一位。。。。
by JK_LOVER @ 2020-08-09 21:26:31
等等，建边也错了。
by JK_LOVER @ 2020-08-09 21:26:42
#include<bits/stdc++.h>
using namespace std;
const int N = 4010;
int read(){
int x = 0,f = 0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return f?-x:x;
}
struct Edge{int to,nxt;}e[N<<1];
int head[N],cnt = 1,st[N],n,m,top = 0,col[N],dfn[N],low[N],tot = 0,tim = 0;
void Init(){
cnt = 1;tot = 0;top = 0;tim = 0;
memset(col,0,sizeof(col));memset(dfn,0,sizeof(col));
memset(low,0,sizeof(low));memset(st,0,sizeof(st));
memset(head,0,sizeof(head));
}
void add(int x,int y){
e[++cnt].nxt = head[x];e[cnt].to = y;head[x] = cnt;
}
void tarjin(int x){
dfn[x] = low[x] = ++tim;st[++top] = x;
for(int i = head[x];i;i = e[i].nxt){
int y = e[i].to;
if(!dfn[y]){
tarjin(y);low[x] = min(low[x],low[y]);
}
else if(!col[y]) low[x] = min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
col[x] = ++tot;
while(st[top] != x){
col[st[top]] = tot;
top--;
}
top--;
}
}
int main(){
int K;
scanf("%d",&K);
while(K--){
Init();
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i++){
char ch1[110],ch2[110];
int a = 0,b = 0;
scanf("%s%s",ch1,ch2);
int len = 1;
while(isdigit(ch1[len])) a=a*10+(int)ch1[len++]-'0';
len = 1;
while(isdigit(ch2[len])) b=b*10+(int)ch2[len++]-'0';
if(ch1[0] == 'm' && ch2[0] == 'h')
{
add(a+n,b+n);add(b,a);
}
if(ch1[0] == 'h' && ch2[0] == 'h')
{
add(a,b+n);add(b,a+n);
}
if(ch1[0] == 'm' && ch2[0] == 'm')
{
add(a+n,b);add(b+n,a);
}
if(ch1[0] == 'h' && ch2[0] == 'm')
{
add(a,b);add(b+n,a+n);
}
}
for(int i = 1;i <= n*2;i++){
if(!dfn[i]) tarjin(i);
}
int a = 0;
for(int i = 1;i <= n;i++){
// cout<<col[i]<<" "<<col[i+n]<<endl;
if(col[i] == col[i+n] && !a){
printf("BAD\n");a=1;
}
}
if(!a) printf("GOOD\n");
}
return 0;
}
by widsnoy @ 2020-08-09 21:53:46
/kk