一道基本跟博弈论毫无关系的题。

维护一个保护集合 SS ，表示哪些点 AA 可能胜利。

首先将所有绿点加入 SS 。

  1. 对于一个不在 SS 的 AA 点，若它存在某个后继在 SS 中，则将其加入 SS 。
  2. 对于一个不在 SS 的 BB 点，若它所有后继都在 SS 中，则将其加入 SS。

通过拓扑排序可以在 O(n+m) 求出 SS 集合，那么剩下的点 AA 必败。

  1. 对于一个在 SS 的 AA 点，若它所有后继都不在 SS ，则将其移除出 SS 。

  2. 对于一个在 SS 的 BB 点，若它存在某个后继不在 SS 中，则将其加入进 SS 。

最后总共时间复杂度为 O(n(n+m))。

code：

#include<stdio.h>
#include<stdbool.h>
int n,m,cnt,c[3030],head[3030],du[3030];
struct node
{
    int next;
	int to;
}e[30300];
void add(int x,int y)
{
    e[++cnt].next=head[x];
    head[x]=cnt;
    e[cnt].to=y;du[y]++;
}
int deg[30300],vis[30300],q[30300];
bool solve()
{
    int t=0,x,h=1;
    for(int i=1;i<=n;i++)
    {
        vis[i]=c[i];
		deg[i]=du[i];
        if(vis[i])
			q[++t]=i;
    }
    while(h<=t)
    	for(int i=head[q[h++]];i;i=e[i].next)
        	if(!vis[e[i].to])
    		{
   	     		x=e[i].to;
        		if(x<=m)
					vis[q[++t]=x]=1;
        		else
        		{
            		deg[x]--;
            		if(!deg[x])
						vis[q[++t]=x]=1;
        		}
    		}
    t=0;
	h=1;
    for(int i=1;i<=n;i++)
    {
        deg[i]=du[i];
        if(!vis[i])
			q[++t]=i;
    }
    while(h<=t)
		for(int i=head[q[h++]];i;i=e[i].next)
    		if(vis[e[i].to])
    		{
        		x=e[i].to;
        		if(x>m)
					vis[q[++t]=x]=0;
        		else
        		{
            		deg[x]--;
            		if(!deg[x])
						vis[q[++t]=x]=0;
        		}
    		}
    t=0;
    for(int i=1;i<=n;i++)
        if(c[i]&&!vis[i])
		{
			c[i]=0;
			t=1;
		}
    return t;
}

int main()
{
    scanf("%d%d",&m,&n);
    n+=m;
    int x,k,t=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&c[i],&k);
        for(int j=1;j<=k;j++)
        {
            scanf("%d",&x);
            add(x,i);
        }
    }
    while(solve());
    for(int i=1;i<=n;i++)
        if(vis[i])
			q[++t]=i;
    printf("%d\n",t);
    for(int i=1;i<=t;i++)
		printf("%d\n",q[i]);
    return 0;
}