#P2948. [Poi2001]绿色游戏

    ID: 2068 传统题 1000ms 512MiB 尝试: 6 已通过: 5 难度: 8 上传者: 标签>CF2500提高+/省选-必胜/必败状态递推最小不动点迭代队列单调量证明终止

[Poi2001]绿色游戏

题目描述

绿色游戏是一种两人游戏,双方分别称 Ann 和 Billy。游戏的内容主要是轮流在棋盘上移动一颗棋子。

棋盘上的点一部分是绿色的,其余是白色的;全部从 11 至 a+ba+b 编号。编号 11 至 aa 的点属于 Ann,编号 (a+1)(a+1) 至 (a+b)(a+b) 的点属于 Billy。每个点都有一些后继点,均可一步到达。属于 Ann 的点的后继点一定属于 Billy,反之亦然。所有的点都至少有一个后继点,这样总可以往下走一步。

游戏开始时把棋子放在任意的一点 PP 上,然后双方轮流移动棋子至当前所在点(属于移动方)的一个后继点上(属于对手)。游戏由点 PP 的拥有者开始,棋子第一次重复到达某个点 QQ 时结束。取棋子从第一次到达 QQ 到第二次到达 QQ 的这段路线,它构成一个环。如果环上至少有一个绿色点(包括 QQ 本身),则 Ann 赢,否则 Billy 赢。第一次到达 QQ 之前经过的点不参与判胜。若从点 PP 开始,不管 Billy 如何移动,Ann 总能保证赢得这次游戏,则称 Ann 对起始点 PP 有必胜的策略。

任务:

编写一个程序,完成下列工作:

  1. 读入对棋盘的描述;
  2. 算出 Ann 有必胜策略的起始点。

输入格式

首行有两个整数 aa 和 bb,两个整数之间用一个空格分开,分别表示属于 Ann 和 Billy 的点数。

以下 a+ba+b 行是对各点的描述,先描述 Ann 的点,再描述 Billy 的点。第 i+1i+1 行(1≤i≤a+b1\le i\le a+b)以整数 z,kz,k 开始:zz 表示点 ii 的颜色(0 表示白色,1 表示绿色),kk 表示后继点的数目。然后是 kk 个整数(1≤k<a+b1\le k<a+b),写在同一行,代表点 ii 后继点的编号,这些整数均用一个空格分开。绿点的个数不超过 100100,所有点的后继点的个数之和不超过 3×1043\times 10^4。

输出格式

首行仅一个整数 LL,代表 Ann 有 LL 个有必胜策略的起始点。以下 LL 行按升序顺序依次给出这些点的编号。

5 3
0 2 6 7
0 3 6 7 8
0 1 8
1 1 7
1 1 8
1 2 1 2
0 2 1 2
0 2 3 4
5
1
2
4
6
7

数据规模与约定

对于 100%100\% 的数据,a,ba,b 为非负整数,1≤a+b≤30001\le a+b\le3000。

题目来源