P6560 [SBCOI2020] 时光的流逝

博弈论水题

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int n,m,qq;
queue<int> q;
int cn;
int cntt[100001];
int tu[100001],ct[100001];
int x,y;
int p;
int sg[100001];
int head[100001];
struct e{
    int to;
    int ne;
}ed[500005];
void add(int f,int to){
    p++;
    ed[p].to=to;
    ed[p].ne=head[f];
    head[f]=p;
}
void ini(){
    for(int i=1;i<=n;++i){
        sg[i]=0;
        ct[i]=tu[i];
    }
    sg[y]=1;
    while(!q.empty())
        q.pop();
    for(int i=1;i<=cn;++i){
        sg[cntt[i]]=1;
        q.push(cntt[i]);

    }
}
void del(int r){
    for(int i=head[r];i;i=ed[i].ne){
        if(sg[ed[i].to]) continue;
        if(sg[r]==1){
            sg[ed[i].to]=2;
            q.push(ed[i].to);
        }else{
            ct[ed[i].to]--;
            if(ct[ed[i].to]==0){
                sg[ed[i].to]=1;
                q.push(ed[i].to);
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&qq);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        add(y,x);
        tu[x]++;
    }
    for(int i=1;i<=n;++i){
        if(tu[i]==0){
            cntt[++cn]=i;
        }
    }
    for(int i=1;i<=qq;++i){
        scanf("%d%d",&x,&y);
        ini();
        q.push(y);
        del(y);
        while(!q.empty()){
            int z=q.front();
            q.pop();
            if(sg[x])
            break;
            del(z);
        }
        if(sg[x]==1){
            printf("-1n");
        }
        if(sg[x]==0){
            printf("0n");
        }
        if(sg[x]==2){
            printf("1n");
        }
    }
    return 0;
}