解题思路

老小区有 n 盏灯、每盏灯各有一个开关；按下第 i 个开关会翻转第 i 盏灯，同时还会额外翻转若干盏灯（给出影响关系）。已知初始状态 a[i]∈{0,1}（0 关、1 开），问是否存在一组开关使所有灯都为 0；若存在，输出按下的开关编号（升序），并在多解中选择

1. 开关数量最少；2) 数量相同则字典序（从小到大序列的字典序）最小。

算法选择：位运算状态压缩 + 子集枚举

• 将每个开关的作用用一个 n 位的位掩码表示：effect[i] 的第 j 位为 1 表示按下 i 会翻转第 j 盏灯。注意第 i 位始终为 1（会翻转自身）。

题目内容

老旧小区需要关闭一排灯，由于接线混乱，按某个灯的开关时可能会同步影响多个灯的状态，被影响的灯的状态会发生反转，即：原先亮着的灯会关闭，而关的灯会打开。

已知第 $i$ 个开关除了改变 $i$ 号灯的状态之外，还会额外影响多个灯的状态；

请问是否存在方案使得所有的灯都关闭，如果无解则输出 $-1$ ，有解时则输出选择按开关数量最小的方案，如果按开关数量相同再比较输出字典序最小的方案。

输入描述

第 $1$ 行两个整数 $n$ 和 $m(1<=n<=20，0<=m<=n*(n-1))$ ,表示 $n$ 个灯(每个灯一个开关)， $m$ 个额外的影响关系。

第 $2$ 行 $n$ 个整数 $a[i]$ 表示灯的初始开关情况，$0$ 表示关闭，$1$ 表示开启 $(0<=a[i]<= 1,1 <=i<=n$ ，表示灯的索引序号)。

第 $3$ 行到第 $m+2$ 行，每行两个整数 $x$ 和 $y$ ，表示对灯 $x$ 进行开关时会额外影响灯 $y$ ，题目保证输入影响关系不重复。

输出描述

如果无解，输出 $-1$ ;

如果有解，输出一行从小到大排序后的整数序列，用空格隔开;

如果有多个可行解，则输出按开关数量最小的方案，数量相同时输出字典序最小的方案。这里字典序最小的比较遵循按相同开关数的方案从小到大排序后，依次从第一个数开始比较，比较到第一个不同的位置时，更小的数所在序列更小。

样例1

输入

2 2
0 1
1 2
2 1

输出

-1

说明

有两盏灯，灯 $1$ 为关闭状态，灯 $2$ 为打开状态;两盏灯的状态是相互影响的，当关闭灯 $2$ 时，灯 $1$ 会从关闭状态变为打开状态;当再次关闭灯 $1$ 时灯 $2$ 状态又会被打开;

所以不存在方案把两盖灯都关闭，因此输出为 $-1$ ;

样例2

输入

3 4
1 0 0
2 1
2 3
3 1
3 2

输出

1

说明

方案一:按下开关 $1$ 后，只有灯 $1$ 自身关闭，此时为 $0$ $0$ $0$ ，满足条件。

方案二:选择 $1$ $2$ $3$ 的方案也可以使得最终值所有灯关闭，也满足条件，但是该方案选取的个数更多，所级输出第一种方案。

样例3

输入

3 3
0 0 1
1 2
1 3
3 2

输出

2 3

说明

当选择开关 $2$ 和 $3$ 之后

按下开关 $2$ 后，没有其他影响的开关，只有灯 $2$ 自身，此时亮灯情况为 $0$ $1$ $1$ 。

按下开关 $3$ 后，格外影响灯 $2$ 、则 $2$ 和 $3$ 分别切换开灯状态，此时为 $0$ $0$ $0$ 所有灯关闭。

提示

(1)如果存在两种方案均满足，其中解法一输出为 $1$ $2$ ，解法二输出为 $1$ $3$ ，根据题目的字典序最小输出要求，最终输出为解法一的答案 $1$ $2$ ;

(2)初始状态下，至少有一盏灯是打开状态;

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写