Dancing Link - 舞蹈链
问题
集合拥有个元素，集合拥有个元素，其中任意是集合的一个子集，包含中元素的数量为（）。
集合是的一个子集，且中的子集所包含的的元素可以覆盖集合。设集合是中所有元素所包含的中元素组成的集合。例如
其中
重复覆盖：对于，存在至少一个使得。例如集合，子集组成，称这样的是的重复覆盖。显然允许两个。
精确覆盖：对于，存在且只存在一个使得。例如集合，子集组成，称这样的是的精确覆盖。显然必然满足。
求集合和子集集合的重复覆盖和精确覆盖。
重复覆盖
设初始时重复覆盖，的所有子集中的元素所组成的集合为。对于，若，则在中寻找满足，将该子集加入重复覆盖中，将所有都加入。每个子集只能加入中一次，不能重复加入。当然也可以用染色来标记所有子集中已经加入的那些元素，防止重复。
遍历完成后即为重复覆盖。求重复覆盖的时间复杂度为。
精确覆盖
设初始时精确覆盖，的所有子集中的元素所组成的集合为。
对于，每个包含的子集都可能是的一员，我们用递归的方式寻找所有可能。利用中任意两子集的交集为空的特性，若且，那么只要，那么必然。
初始时将中的所有子集标记为白色（未被使用过）。遍历的所有元素，进行以下步骤：
若，这时有个候选子集（非红色，即未被使用过），它们都包含。遍历这个候选子集，假定选择加入，将所有加入。然后将中所有包含中元素的其他子集染红（标记为已被使用）；
重复上述过程只有两种结果：
所有都已经加入，这时的即为精确覆盖；
所有还没都加入，这时所有的子集都已经被染红。说明上次在候选子集中做出的选择是错的。
我们需要记录每次选择时染红了哪些子集，以及当时遍历到的元素。将这次选择回退，把当时染红的子集重新染回白色，然后选择下一个候选者，再重复上述过程，指导找到精确覆盖。该过程是递归的。
下面演示舞蹈链算法：
其中。
用行来表示子集，列来表示集合中的元素，可得行列矩阵：
舞蹈链算法用十字链表这种特别的数据结构将所有元素串联起来，坐标为的节点下标是，表示。沿着十字链表的行可以遍历子集的所有元素，沿着十字链表的列可以遍历所有包含的子集。
对于上图中的示例，元素的候选子集有，假定选择，可得，然后将所有包含中元素的子集染红（）；
接着考虑元素，其候选子集有，但它们都被染红了无法使用，这时不存在一个可用的子集，说明上一轮选择错误。不选择上一轮的，将染回白色，假定选择，可得，染红；
再次考虑元素，其候选子集有（已被染红），假定选择，可得，染红（上一轮已被染红）；
元素，因此可以直接跳过；
考虑元素，其候选子集有（已被染红），假定选择，可得，染红（之前已被染红）；
元素，可以直接跳过。至此，所有元素都被覆盖到，并且中任意两子集的交集为空，算法结束。
其实十字链表并不需要“染红”这个操作来标记一个子集是否可以使用，而是用添加、删除来操作链表上的节点。例如元素选择子集时，将节点从头节点一行中删除，将包含的子集（包括自己）的元素也从所在的列中删除。如图所示：
仔细观察可知，删除之后仍然能够判定包含元素（拥有列关系），且可知（，拥有行关系）。这些遗留的列表指针可以恢复错误选择。对于子集上的所有元素进行相同的链表操作，等价于将染红：
若尝试所有子集组合后仍无法找出精确覆盖，则说明该条件下不存在精确覆盖。舞蹈链算法的时间复杂度与递归的时间复杂度一样是。