张钧皓 @ 2018-07-28 14:20:36
我是连两个点,不知是连错了还是tarjan错了
麻烦过路大佬帮查错
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#define ll long long
#define M 1005
using namespace std;
inline ll read()
{
ll d=0,w=1;
char c=getchar();
while(c!='-'&&(c<'0'||c>'9'))
c=getchar();
if(c=='-')
{
w=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
d=d*10+c-'0';
c=getchar();
}
return d*w;
}
ll n,m;
struct edge
{
ll next,to;
} e[M];
ll head[M],cnt=0;
void adde(ll x,ll y)
{
cnt++;
e[cnt].next=head[x];
e[cnt].to=y;
head[x]=cnt;
}
ll dfn[M],low[M],ot=0;
stack <ll> S;
bool instack[M];
ll tos=0;
ll belong[M];
void tarjan(ll x)
{
dfn[x]=low[x]=++ot;
instack[x]=1;
S.push(x);
ll v;
for(ll i=head[x];i;i=e[i].next)
{
v=e[i].to;
if(!dfn[v])
{
tarjan(v);
low[x]=min(low[x],low[v]);
}
else
if(instack[v])
{
low[x]=min(low[x],dfn[v]);
}
if(low[x]==dfn[x])
{
ll top;
++tos;
while(!S.empty()&&S.top()!=x)
{
top=S.top();
instack[top]=0;
belong[top]=tos;
S.pop();
}
if(!S.empty())
{
instack[x]=0;
belong[x]=tos;
S.pop();
}
}
}
}
string s1,s2;
int main()
{
ll k=read(),x;
for(ll r=1;r<=k;r++)
{
while(!S.empty())
S.pop();
memset(e,0,sizeof(e));
memset(dfn,0,sizeof(dfn));
memset(instack,0,sizeof(instack));
memset(belong,0,sizeof(belong));
memset(low,0,sizeof(low));
memset(head,0,sizeof(head));
ot=0;
tos=0;
cnt=0;
n=read();
m=read();
for(ll i=1;i<=m;i++)
{
cin>>s1>>s2;
adde(2*(s1[1]-'0')-(s1[0]=='h'?0:1),2*(s2[1]-'0')-(s2[0]=='h'?1:0));
adde(2*(s2[1]-'0')-(s2[0]=='h'?0:1),2*(s1[1]-'0')-(s1[0]=='h'?1:0));
}
bool f=0;
for(ll i=1;i<=2*n;i++)
if(!dfn[i])
{
tarjan(i);
}
for(ll i=1;i<=2*n;i++)
{
if(belong[i]==belong[((i-1)^1)+1])
{
f=1;
break;
}
}
if(f==0)
cout<<"GOOD"<<endl;
else
cout<<"BAD"<<endl;
}
}
by Tyher @ 2018-09-26 17:32:49
@张钧皓