思路是不是错了

P4171 [JSOI2010] 满汉全席

张钧皓 @ 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

@张钧皓

只连两个考虑不到所有情况的

|