解题思路

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

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

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

• 将每个开关的作用用一个 n 位的位掩码表示：effect[i] 的第 j 位为 1 表示按下 i 会翻转第 j 盏灯。注意第 i 位始终为 1（会翻转自身）。
• 将初始状态也表示为 n 位掩码 S（第 i 位为 1 表示第 i 盏灯初始为开）。
• 对所有开关集合的子集 mask (0..2^n-1) 枚举，表示要按下的开关集合。 该方案的最终状态为：S XOR effect[i] 对 mask 中的每个 i 叠加一次。若结果为 0，即为可行方案。
• 在可行方案之间，先比较 popcount(mask)（开关数量），更小者优先；若相同，进行字典序比较：从开关 1 到 n 依次比较两方案在该位置是否选择（位是否为 1），在第一个不同的位置，取 1 的那个方案更小（因为它包含了更小的编号）。

备注：本题也可用线性代数的思想建模为 A*x=a (mod 2)，用模 2 高斯消元得到一组解并在零空间中找最优解。但由于 n ≤ 20，直接枚举 2^n 个子集即可稳妥通过，代码也更简洁。

复杂度分析

• 时间复杂度：O(n * 2^n)（对每个子集处理至多 n 个开关或用位运算按最低位迭代）。在 n ≤ 20 时约千万级操作，可接受。
• 空间复杂度：O(n)（只需存储每个开关的作用掩码与常数额外变量）。

代码实现

Python

# -*- coding: utf-8 -*-
# 题意实现放在外部函数中；主函数负责输入输出（ACM 风格）

import sys

def lex_smaller(mask_a, mask_b, n):
    """在相同开关数量下，比较两方案的字典序（升序序列）。
       从1到n依次看位，第一处不同时，位为1的方案更小。"""
    if mask_b is None:
        return True
    for i in range(n):
        a_bit = (mask_a >> i) & 1
        b_bit = (mask_b >> i) & 1
        if a_bit != b_bit:
            return a_bit == 1
    return False  # 完全相同

def solve(n, m, a_list, edges):
    # 每个开关的作用掩码，包含自身
    effect = [0] * n
    for i in range(n):
        effect[i] |= (1 << i)
    for x, y in edges:
        # 输入为1-based，转成0-based
        effect[x - 1] |= (1 << (y - 1))

    # 初始状态掩码
    S = 0
    for i, v in enumerate(a_list):
        if v == 1:
            S |= (1 << i)

    best_mask = None
    best_cnt = 1 << 30

    # 枚举所有按键的子集
    total = 1 << n
    for mask in range(total):
        cur = S
        t = mask
        # 逐个最低位处理能更快
        while t:
            lsb = t & -t
            idx = (lsb.bit_length() - 1)  # 第 idx 个开关被按
            cur ^= effect[idx]
            t -= lsb
        if cur == 0:
            cnt = mask.bit_count()
            if cnt < best_cnt or (cnt == best_cnt and lex_smaller(mask, best_mask, n)):
                best_cnt = cnt
                best_mask = mask

    if best_mask is None:
        return None
    # 输出升序编号
    ans = []
    for i in range(n):
        if (best_mask >> i) & 1:
            ans.append(i + 1)
    return ans

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        return
    it = iter(data)
    n = next(it)
    m = next(it)
    a_list = [next(it) for _ in range(n)]
    edges = [(next(it), next(it)) for _ in range(m)]
    res = solve(n, m, a_list, edges)
    if res is None:
        print(-1)
    else:
        print(" ".join(map(str, res)))

if __name__ == "__main__":
    main()

Java

// ACM 风格：主类名统一为 Main，主函数读写；核心逻辑放外部静态函数
import java.util.*;

public class Main {

    // 在相同开关数量下比较字典序：从小到大编号，第一处不同时，位为1的更小
    static boolean lexSmaller(long a, long b, int n) {
        if (b == -1L) return true;
        for (int i = 0; i < n; i++) {
            long ab = (a >> i) & 1L;
            long bb = (b >> i) & 1L;
            if (ab != bb) return ab == 1L;
        }
        return false;
    }

    // 返回方案（升序编号），无解返回空列表
    static List<Integer> solve(int n, int m, int[] a, int[][] edges) {
        long[] effect = new long[n];
        for (int i = 0; i < n; i++) effect[i] |= (1L << i);
        for (int i = 0; i < m; i++) {
            int x = edges[i][0];
            int y = edges[i][1];
            effect[x - 1] |= (1L << (y - 1));
        }

        long S = 0;
        for (int i = 0; i < n; i++) if (a[i] == 1) S |= (1L << i);

        long bestMask = -1L;
        int bestCnt = Integer.MAX_VALUE;

        long total = 1L << n;
        for (long mask = 0; mask < total; mask++) {
            long cur = S;
            long t = mask;
            // 逐个最低位处理以加速
            while (t != 0) {
                int idx = Long.numberOfTrailingZeros(t);
                cur ^= effect[idx];
                t &= (t - 1);
            }
            if (cur == 0) {
                int cnt = Long.bitCount(mask);
                if (cnt < bestCnt || (cnt == bestCnt && lexSmaller(mask, bestMask, n))) {
                    bestCnt = cnt;
                    bestMask = mask;
                }
            }
        }

        if (bestMask == -1L) return Collections.emptyList();
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) if (((bestMask >> i) & 1L) == 1L) ans.add(i + 1);
        return ans;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        if (!in.hasNextInt()) return;
        int n = in.nextInt();
        int m = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = in.nextInt();
        int[][] edges = new int[m][2];
        for (int i = 0; i < m; i++) {
            edges[i][0] = in.nextInt();
            edges[i][1] = in.nextInt();
        }
        List<Integer> res = solve(n, m, a, edges);
        if (res.isEmpty()) {
            System.out.println(-1);
        } else {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < res.size(); i++) {
                if (i > 0) sb.append(' ');
                sb.append(res.get(i));
            }
            System.out.println(sb.toString());
        }
        in.close();
    }
}

C++

// ACM 风格：主函数读写，核心逻辑放外部函数
#include <bits/stdc++.h>
using namespace std;

// 在相同开关数量下比较字典序（升序编号序列）：从1到n找第一处不同，位为1的方案更小
bool lexSmaller(unsigned int a, unsigned int b, int n) {
    if (b == UINT_MAX) return true; // 用作“未赋值”的标记
    for (int i = 0; i < n; ++i) {
        bool ab = (a >> i) & 1u;
        bool bb = (b >> i) & 1u;
        if (ab != bb) return ab; // ab==1 代表包含更小的编号
    }
    return false;
}

// 返回方案（升序编号），无解返回空vector
vector<int> solve(int n, int m, const vector<int>& a, const vector<pair<int,int>>& edges) {
    vector<unsigned int> effect(n, 0);
    for (int i = 0; i < n; ++i) effect[i] |= (1u << i);
    for (auto &e : edges) {
        int x = e.first, y = e.second;
        effect[x - 1] |= (1u << (y - 1));
    }
    unsigned int S = 0;
    for (int i = 0; i < n; ++i) if (a[i] == 1) S |= (1u << i);

    unsigned int bestMask = UINT_MAX;
    int bestCnt = INT_MAX;

    unsigned int total = 1u << n;
    for (unsigned int mask = 0; mask < total; ++mask) {
        unsigned int cur = S, t = mask;
        while (t) {                    // 逐个最低位处理
            unsigned int lsb = t & -t; // 取最低位
            int idx = __builtin_ctz(t);
            cur ^= effect[idx];
            t -= lsb;
        }
        if (cur == 0u) {
            int cnt = __builtin_popcount(mask);
            if (cnt < bestCnt || (cnt == bestCnt && lexSmaller(mask, bestMask, n))) {
                bestCnt = cnt;
                bestMask = mask;
            }
        }
    }

    if (bestMask == UINT_MAX) return {};
    vector<int> ans;
    for (int i = 0; i < n; ++i)
        if ((bestMask >> i) & 1u) ans.push_back(i + 1);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<pair<int,int>> edges(m);
    for (int i = 0; i < m; ++i) {
        int x, y; cin >> x >> y;
        edges[i] = {x, y};
    }
    vector<int> res = solve(n, m, a, edges);
    if (res.empty()) {
        cout << -1 << "\n";
    } else {
        for (int i = 0; i < (int)res.size(); ++i) {
            if (i) cout << ' ';
            cout << res[i];
        }
        cout << "\n";
    }
    return 0;
}

题目内容

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

已知第 $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)初始状态下，至少有一盏灯是打开状态;