[JSOI2010]满汉全席

C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 480K, 提交时间: 2019-07-26 15:59:03

#include <bits/stdc++.h>
using namespace std;
const int N=2005,M=20005,inf=0x3fffffff;
int head[N],ver[M<<1],nex[M<<1];
int dfn[N],low[N],bel[N],q[N<<1],m,n,scc;
bool inq[N];
int tot=1,t=0,T,top=0;
void add (int u,int v) {
    ver[++tot]=v;nex[tot]=head[u];head[u]=tot;
}

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int get () {
    int x;
    char c=getchar();
    while (c!='m'&&c!='h') c=getchar();
    if (c=='m') x=read()*2;
    else x=read()*2+1;
    return  x;
}

void Tarjan (int x) {
    dfn[x]=low[x]=++t;
    q[++top]=x;inq[x]=1;
    for (int i=head[x];i;i=nex[i])
        if (!dfn[ver[i]]) {
            Tarjan(ver[i]);
            low[x]=min(low[x],low[ver[i]]);
        }
        else if (inq[ver[i]])
            low[x]=min(low[x],dfn[ver[i]]);
    if (low[x]==dfn[x]) {
        scc++;
        int now=0;
        while (now!=x) {
            now=q[top--];
            bel[now]=scc;
            inq[now]=0;
        }
    }
}

int main () {
    T=read();
    while (T--) {
        memset(head,0,sizeof(head));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(bel,0,sizeof(bel));
        memset(inq,0,sizeof(inq));
        tot=1,t=m=n=scc=top=0;
        n=read(); m=read();
        int x,y,xp,yp;
        for (int i=1;i<=m;i++) {
            x=get(); y=get();
            xp=x^1;yp=y^1;
            add(xp,y);add(yp,x);
        }
        bool flag=0;
        for (int i=2;i<=2*n+1;i++)
            if (!dfn[i]) Tarjan(i);
        for (int i=1;i<=n;i++)
            if (bel[2*i]==bel[2*i+1])
                { puts("BAD");flag=1;break; }
        if (!flag) puts("GOOD");
    }
    return 0;
}

Python3(3.5.2) 解法, 执行用时: 51ms, 内存消耗: 3480K, 提交时间: 2020-09-22 17:59:53

def tarjan(i):
    global time, cnt
    time += 1
    dfn[i] = time
    low[i] = time
    stack.append(i)
    if i in edges:
        for j in edges[i]:
            if j in stack:
                # low[i] = low[j]
                low[i]=min([low[i],dfn[j]])
            elif dfn[j] == 0:
                tarjan(j)
                low[i] = min([low[i], low[j]])
    if low[i] == dfn[i]:
        out = stack.pop(-1)
        belong[out] = cnt
        while out != i:
            out = stack.pop(-1)
            belong[out] = cnt
        cnt += 1


K = int(input())
for _ in range(K):
    n, m = map(int, input().split())
    edges = {}
    for _ in range(m):
        c1, c2 = input().split()
        c1 = int(c1[0] == 'h') * n + int(c1[1:]) - 1
        c2 = int(c2[0] == 'h') * n + int(c2[1:]) - 1
        _c1 = c1 + n if c1 < n else c1 - n
        _c2 = c2 + n if c2 < n else c2 - n
        if _c1 in edges:
            edges[_c1].append(c2)
        else:
            edges[_c1] = [c2]
        if _c2 in edges:
            edges[_c2].append(c1)
        else:
            edges[_c2] = [c1]
    dfn = [0 for _ in range(2 * n)]
    low = [0 for _ in range(2 * n)]
    belong = [0 for _ in range(2 * n)]
    time = 0
    cnt = 0
    stack = []
    for i in range(2 * n):
        if not dfn[i]:
            tarjan(i)
    mark = 0
    for i in range(n):
        if belong[i]==belong[i + n]:
            print('BAD')
            mark = 1
            break
    if mark == 0:
        print('GOOD')

C++ 解法, 执行用时: 4ms, 内存消耗: 496K, 提交时间: 2021-11-25 19:43:42

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//const int inf=0x7fffffff;
const int inf=0x3f3f3f3f;
const int maxn=4e3+5;
int t,n,m,t1,f1,head[405],vis[405],f[405],cou,q[405],cou1,cou2,head1[405];
char a,c;
int b,d;
struct G
{
    int to,next;
}g[maxn],g1[maxn];
void add_edge(int x,int y){g[++cou]={y,head[x]},head[x]=cou;g1[++cou2]={x,head1[y]},head1[y]=cou2;}
int opp(int x)
{
    if(x>n) return x-n;
    return x+n;
}
void dfs1(int x)
{
    vis[x]=1;
    for(int i=head[x];i;i=g[i].next)
    {
        int k=g[i].to;
        if(!vis[k]) dfs1(k);
    }
    q[++cou1]=x;
}
void dfs2(int x,int y)
{
    vis[x]=0;
    f[x]=y;
    for(int i=head1[x];i;i=g1[i].next)
    {
        int k=g1[i].to;
        if(vis[k]) dfs2(k,y);
    }
}
void solve()
{
    cin>>n>>m;
    cou=cou1=cou2=0;
    for(int i=1;i<=2*n;i++) f[i]=i,head1[i]=0,head[i]=0;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>c>>d;
        if(a=='h') b+=n;
        if(c=='h') d+=n;
        add_edge(opp(b),d),add_edge(opp(d),b);
    }
    for(int i=1;i<=2*n;i++)
    {
        if(!vis[i]) dfs1(i);
    }
    for(int i=cou1;i>=1;i--)
    {
        if(vis[q[i]]) dfs2(q[i],q[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(f[i]==f[i+n])
        {
            puts("BAD");
            return;
        }
    }
    puts("GOOD");
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

详情