Dino_chx @ 2023-06-21 15:53:46

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+7;
vector<int> g[N];
stack<int> s;
int n,m,dfn[N],vis[N],low[N],color[N],num[N],colornum,cnt;
void paint(int x)
{
    s.pop();
    color[x]=colornum;
    num[colornum]++;
    vis[x]=0;
    return;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++cnt;
    s.push(x);
    vis[x]=true;
    for(auto q:g[x])
    {
        if(!dfn[q])
        {
            tarjan(q);
            low[x]=min(low[x],low[q]);
        }
        else if(vis[q])
            low[x]=min(low[x],dfn[q]);
    }
    if(low[x]==dfn[x])
    {
        colornum++;
        while(s.top()!=x)
        {
            int t=s.top();
            paint(t);
        }
        paint(x);
    }
    return;
}
void init(int pp)
{
    colornum=cnt=0;
    memset(dfn,0,sizeof dfn);
    memset(vis,0,sizeof vis);
    memset(low,0,sizeof low);
    memset(color,0,sizeof color);
    memset(num,0,sizeof num);
    while(!s.empty())
    {
        s.pop();
    }
    for(int i=0;i<=pp*2;i++)
    {
        g[i].clear();
    }
    return; 
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        init(n);
        for(int i=1;i<=m;i++)
        {
            char xa,xb;
            int a,b;
            scanf(" %c%d %c%d",&xa,&a,&xb,&b);
            bool pa=(xa=='m'),pb=(xb=='m');
            g[a+n*(pa&1)].push_back(b+n*(pb^1));
            g[b+n*(pb&1)].push_back(a+n*(pa^1));      
        }
        for(int i=1;i<=(n<<1);i++)
        {
            if(!dfn[i])
                tarjan(i);
        }
        for(int i=1;i<=n;i++)
        {
            if(color[i]==color[i+n])
            {
                puts("BAD");
                return 0;
            }
        }
        puts("GOOD");
    }
    return 0;
}

by 灵华 @ 2023-06-21 16:35:21

@clancysam 仔细读读题目范围。

我之前也错在这里了。他样例是数字只有一位，但是数据可能不止一位。

by bzzltl @ 2023-06-21 16:38:14

@clancysam

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+7;
vector<int> g[N];
stack<int> s;
int n,m,dfn[N],vis[N],low[N],color[N],num[N],colornum,cnt;
void paint(int x)
{
    s.pop();
    color[x]=colornum;
    num[colornum]++;
    vis[x]=0;
    return;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++cnt;
    s.push(x);
    vis[x]=true;
    for(int i=0;i<g[x].size();i++)
    {
        int q=g[x][i];
        if(!dfn[q])
        {
            tarjan(q);
            low[x]=min(low[x],low[q]);
        }
        else if(vis[q])
            low[x]=min(low[x],dfn[q]);
    }
    if(low[x]==dfn[x])
    {
        colornum++;
        while(s.top()!=x)
        {
            int t=s.top();
            paint(t);
        }
        paint(x);
    }
    return;
}
void init(int pp)
{
    colornum=cnt=0;
    memset(dfn,0,sizeof dfn);
    memset(vis,0,sizeof vis);
    memset(low,0,sizeof low);
    memset(color,0,sizeof color);
    memset(num,0,sizeof num);
    while(!s.empty())
    {
        s.pop();
    }
    for(int i=0;i<=pp*2;i++)
    {
        g[i].clear();
    }
    return; 
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        init(n);
        for(int i=1;i<=m;i++)
        {
            char xa,xb;
            int a,b;
            scanf(" %c%d %c%d",&xa,&a,&xb,&b);
            bool pa=(xa=='m'),pb=(xb=='m');
            g[a+n*(pa&1)].push_back(b+n*(pb^1));//
            g[b+n*(pb&1)].push_back(a+n*(pa^1));//  
        }
        for(int i=1;i<=(n<<1);i++)
        {
            if(!dfn[i])
                tarjan(i);
        }
        int pd=0;
        for(int i=1;i<=n;i++)
        {
            if(color[i]==color[i+n])
            {
                puts("BAD");
                pd=1;
                break;
//              return 0;
            }
        }
        if(!pd) puts("GOOD");
    }
    return 0;
}

by bzzltl @ 2023-06-21 16:39:42

@clancysam

你那个，输出NO的时候，直接return 0;结束程序了……

改了就过了。

其他的改动忽视一下。

by Dino_chx @ 2023-06-21 17:01:30

@bzzltl

OK 谢谢，已经关注

此贴结

by ax_by_c @ 2023-06-21 20:25:28

<h1>此贴结</h1>