我有一个双边图，一侧有 N 个节点，另一侧有近 100 个节点。现在我需要计算匹配项，以便第一部分中的每个节点都与另一部分中的某个节点有链接，这样第一部分中没有两个节点与第二部分中的相同节点匹配。（就像一个工作可以分配给一个仅限申请人）
现在我知道找到这个计数并不容易，而且是#P-hard 问题（来自链接：https ://cs.stackexchange.com/questions/19924/counting-and-finding-all-perfect-maximum-matchings-in -一般图）
但是这样做的残酷解决方案是什么？有人可以用一些代码或伪代码解释一下。
假设输入就像我们有 X 对显示 u 连接到 v
如果 N=2 和 X=4 并且对是 (1,1),(1,2),(2,3),(2,4)。
小 N 可能有动态规划解决方案，其中 2^N 是一个实际的数字。
用 N x 100 表表示图形，当存在从一侧到另一侧的链接时，条目标记为 true。对于 i = 1..100，我们将计算出 Count(i, x)，其中 x 在 0..2^N-1 范围内，表示 N 侧的一组节点。Count(i, x) 将是 N 侧的集合 x 中的节点与 100 侧的前 i 个节点之间的匹配数的计数。
我们可以通过考虑 i 与 x 中的一个节点之间存在匹配的情况以及不匹配的情况，从 Count(i-1, *) 中计算出 Count(i, x)。没有分数的情况 Count(i - 1, x) - 不使用 i 创建匹配的方式数。对于 x 中的每个设置位，如果存在从 i 到由该位表示的节点的链接，则设 y 为未设置该位的 x 的位模式，并将 Count(i - 1, y) 添加到计数中. Count(i, x) 是所有这些计数的总和。
最终答案是 Count(100, 2^N-1) - 一侧的前 100 个节点与另一侧的所有 N 个节点之间的匹配数。