将整数数组划分为 2 个不相连的部分
Partition an integer array into 2 unconnected parts
给定一个 int 数组（每个元素的值等于它的索引），长度为 n 并且数组元素之间的连接为 m。将数组分成 2 部分（相对于给定的 m 连接，部分中的所有元素必须 未连接 。
如果存在这样的分区则输出true，否则false.
这里有 3 个例子：
给定数组：{0, 1, 2, 3}
给定连接：0-1，2-3（0 连接到 1，2 连接到 3）
输出应为：true（分区为{0,3}、{1,2}）
给定数组：{0, 1, 2}
给定连接：1-2、0-1、0-2
输出应为：false（没有 2 个分区仅包含未连接的元素）
给定数组：{0,1}
给定连接：0-1
输出应为：true（分区为{0}、{1}）
我目前的方法：形成数组元素之间的所有可能连接并存储它们，从我存储的连接中删除 m 传入连接，检查剩余连接是否形成给定数组的 2 个分区。这个解决方案太慢了（我怀疑建立所有可能的连接需要太多时间）。
问题是测试给定的图是否是bipartite, i.e. 2-colorable, which can be done efficiently by using depth-first search。从任意节点开始，为其分配两种颜色中的任何一种。对于迭代的每条边，为目标节点赋予与其父节点不同的颜色。如果这不可能，则终止搜索，因为输入不是二分的。否则，您已经生成了表示两个分区的图形的二次着色。
给定一个 int 数组（每个元素的值等于它的索引），长度为 n 并且数组元素之间的连接为 m。将数组分成 2 部分（相对于给定的 m 连接，部分中的所有元素必须 未连接 。
如果存在这样的分区则输出true，否则false.
这里有 3 个例子：
给定数组：
{0, 1, 2, 3}给定连接：
0-1，2-3（0 连接到 1，2 连接到 3）输出应为：
true（分区为{0,3}、{1,2}）给定数组：
{0, 1, 2}给定连接：
1-2、0-1、0-2输出应为：
false（没有 2 个分区仅包含未连接的元素）给定数组：
{0,1}给定连接：
0-1输出应为：
true（分区为{0}、{1}）
我目前的方法：形成数组元素之间的所有可能连接并存储它们，从我存储的连接中删除 m 传入连接，检查剩余连接是否形成给定数组的 2 个分区。这个解决方案太慢了（我怀疑建立所有可能的连接需要太多时间）。
问题是测试给定的图是否是bipartite, i.e. 2-colorable, which can be done efficiently by using depth-first search。从任意节点开始，为其分配两种颜色中的任何一种。对于迭代的每条边，为目标节点赋予与其父节点不同的颜色。如果这不可能，则终止搜索，因为输入不是二分的。否则，您已经生成了表示两个分区的图形的二次着色。