algorithm - 构造任何具有度约束的二分图

Question

我们需要构造一个二分图，每个图有 N 个顶点，在两个部分上，边的总数等于 M。

• 左边的顶点从1到N编号。
• 右边的顶点也从1到N编号。
• 每个顶点大于或等于X且小于或等于Y的度数。即对于所有v，X ≤ deg(v) ≤ Y

给定四个整数 N、M、X、Y，我们需要构造一些满足此属性的二分图。如果不存在任何这样的图，则也告诉同样的。

例子: 如果 N=2 , M=3 , X=1 和 Y=2 那么二分图中的3条边将是:(1,1)，(2,2)和(1,2)

如果 N=2 、 M=3 、 X=1 和 Y=1 则不存在二分图。

这个问题怎么解决

1 ≤ N ≤ 100
1 ≤ X ≤ Y ≤ N 
0 ≤ M ≤ N * N

原始问题 link

Answer 1

显然，变量需要满足:

X * N <= M <= Y * N

否则无解。

寻找边缘可以在波浪中完成。首先将第一组中的每个节点 i 连接到第二组中相应的节点 i。在下一波中，将 i 与 (i + 1) mod N 连接起来。然后 i 和 (i + 2) mod N 等等。这将在每个波浪中将每个顶点的度数增加一个。每当您构建了 M 边时就停止。这也可能发生在波浪期间。