我有一个任务，其中有一个 n x n 板（n<=1e5) I have m buttons on it (min(n^2, 2e5)) I need to run at least one button in such a way so that the sum of the buttons in each row and column is of the same parity.
输入： 中号 x1,y1 x2,y2 ... xm，ym。
这些依次是板边的长度、板按钮的数量以及按钮的位置。
输出：
如果答案不存在，我必须输出“NO”。 否则，我需要输出“YES”，以及输入中这些按钮的索引。
我的解决方案尝试： 我发现在每行和每列中的按钮总和的情况下 是偶数且存在这样的答案，则顶点（按钮） 通过与同一行或同一列中的另一个顶点合并形成一种循环，但这些信息并不能真正给我任何东西，计算复杂度仍然很高。 有人会给出如何解决这个问题的提示/想法吗？ 预先感谢。
总结：
我们有一个全零的 NxN 网格。有些单元具有将其单元的奇偶校验设置为 1 的按钮。我们必须至少按下一个按钮，但可以按下任意数量的按钮。我们能否有效地确定一组至少 1 次按钮按下是否会给每个 rowsum 和每个 colsum 相同的奇偶校验？
制作一个二分图，其中一侧的每行有一个顶点，另一侧的每列有一个顶点，以及连接行和列的每个按钮的边。
如果该图中存在任何循环，则答案是“是”。
有很多方法可以检测无向图中的循环。考虑到您输入的具体形式，我将使用不相交的集合数据结构，如Kruskal算法中那样，这样我就不必实际构建图表。