K算法模板,哪里打错了QAQ

P4171 [JSOI2010] 满汉全席

陰陽さん @ 2021-03-26 21:07:48

#include<bits/stdc++.h>
using namespace std;
int m,n,tot=0,T;
int v[200010],q[200010];//,jie[10010],ud[10010];
vector<int>p[200010],fp[200010];
int exx(int x){
    if(x<=n)return x+n;
    return x-n;
}
void ex(int x,int a,int y,int b){
    int w=x,z=y;
    if(a)x+=n;else w+=n;
    if(b)y+=n;else z+=n;
    p[w].push_back(y);
    p[z].push_back(x);
    fp[y].push_back(w);
    fp[x].push_back(z);
}
void dfs1(int x){
    v[x]=1;
    int i,j,k,l=fp[x].size();
    for(i=0;i<l;i++){
        k=fp[x][i];
        if(!v[k])dfs1(k);
    }
    q[++tot]=x;
}
int dfs2(int x,int y){
    v[x]=0;
    if(x==y)return 1;
    int i,j,k,l=p[x].size();
    for(i=0;i<l;i++){
        k=p[x][i];
        if(v[k])
            if(dfs2(k,y))return 1;
    }
    return 0;
}
int main(){
    cin>>T;
    while(T--){
        cin>>n>>m;
        int i,j,k,fl=0,x,y,a,b;tot=0;
        memset(v,0,sizeof v);
        memset(q,0,sizeof q);
        for(i=0;i<=n;i++)p[i].clear(),fp[i].clear();

        string s1,s2;
        while(m--){
            cin>>s1>>s2;
            if(s1[0]=='m')a=0;else a=1;
            if(s2[0]=='m')b=0;else b=1;
            x=0;for(i=1;i<s1.size();i++)x=x*10+s1[i]-'0';
            y=0;for(i=1;i<s2.size();i++)y=y*10+s2[i]-'0';
    //      printf("(%d %d %d %d)\n",x,a,y,b);
            ex(x,a,y,b);
        }
        for(i=1;i<=n*2;i++){
            if(!v[i])dfs1(i);
        }
        while(tot){
            if(v[q[tot]])
                if(dfs2(q[tot],exx(q[tot]))){
                    cout<<"BAD"<<endl,fl=1;break;
                }
            tot--;
        }
        if(!fl){
            cout<<"GOOD"<<endl;
        }
    }
    return 0;
}

by 陰陽さん @ 2021-04-18 21:04:54

劳资AC了哈哈哈哈


|