P3794.第2题-关灯方案
题目内容
老旧小区需要关闭一排灯，由于接线混乱，按某个灯的开关时可能会同步影响多个灯的状态，被影响的灯的状态会发生反转，即：原先亮着的灯会关闭，而关的灯会打开。
已知第 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.逐行代码手写
