第二十次CCF计算机软件能力认证 第三题 点亮数字人生（拓扑序）

#include<bits/stdc++.h>
using namespace std;
const int N=3010,M=10010;
int m,n,e[N],ne[N],idx,h[N],q,t,f[N],d[N],val[N];//m是点数 n是元件数
vector<int>in[M],out[M],ans;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    d[b]++;
}
string duizhao[]={"NOT","AND","OR","XOR","NAND","NOR"};
int get(char *s){
    for(int i=0;i<6;i++){
        if(duizhao[i]==s)return i;
    }
    return -1;
}
int topsort(){
    queue<int>q;
    for(int i=1;i<=n+m;i++)if(!d[i])q.push(i);
    while(q.size()){
        int now=q.front();q.pop();
        ans.push_back(now);
        for(int i=h[now];~i;i=ne[i]){
            int j=e[i];
            if(--d[j]==0){
                q.push(j);
            }
        }
    }
    return ans.size()==n+m;
}
int main(){
    scanf("%d",&t);
    while(t--){
        memset(h, -1, sizeof h);
        memset(d,0,sizeof d);
        idx=0;
        ans.clear();
        scanf("%d%d", &m, &n);
        char op[100];
        int cnt=0;
        for(int i=1;i<=n;i++){
            scanf("%s%d",op,&cnt);
            f[i+m]=get(op);
            for(int j=0;j<cnt;j++){
                scanf("%s",op);
                if(*op=='O')add(atoi(op+1)+m,i+m);
                else add(atoi(op+1),i+m);
            }
        }
        scanf("%d",&q);
        for(int i=0;i<q;i++){
            in[i].clear();
            for(int j=0;j<m;j++){
                int x;
                scanf("%d",&x);
                in[i].push_back(x);
            }
        }
        for(int i=0;i<q;i++){
            out[i].clear();
            int x;
            scanf("%d",&x);
            for(int j=0;j<x;j++){
                int tep;
                scanf("%d",&tep);
                out[i].push_back(tep);
            }
        }
        if(!topsort()){
            puts("LOOP");
        }
        else{
            for(int i=0;i<q;i++){
                int k=ans.size();
                for(int j=1;j<=m;j++)val[j]=in[i][j-1];
                for(int j=m+1;j<=m+n;j++){
                    int id=f[j];
                    if(id==1||id==5)val[j]=1;
                    else val[j]=0;
                }
                for(int j=0;j<k;j++){
                    int num=ans[j];
                    for(int i=h[num];~i;i=ne[i]){
                        int next=e[i],id=f[next];
                        if(id==0)val[next]=!val[num];
                        else if(id==1)val[next]&=val[num];
                        else if(id==2)val[next]|=val[num];
                        else if(id==3)val[next]^=val[num];
                        else if(id==4)val[next]|=(!val[num]);
                        else val[next]&=(!val[num]);
                    }
                }
                for(int ou:out[i]){
                    printf("%d ",val[ou+m]);
                }
                puts("");
            }
            
        }
    }
    
    
}