algorithm - 找出无向图的最大子集

Question

输入:一个顶点列表和一个邻接列表。

输出:好的顶点的最大子集。

(如果子集中至少有 2 个相邻顶点和至少 2 个不相邻顶点，则我们称该子集中的顶点为“好顶点”。)

示例 1:

Vertexes: [1, 2, 3, 4, 5]
Relations: [(1,2), (1,3), (3,4), (3,5), (4,5)]

output: []

例子2:

output: [1,2,3,4,5,6]

因为对于输出中的每个顶点，它至少有 2 个顶点与其相连，并且至少有 2 个顶点未与其相连。

Answer 1

如果一个顶点在图中至少有两个邻居和至少两个非邻居，则称它为“okay”。顶点必须可以在输出中。

从图中删除所有不合格的顶点。执行此操作时，以前正常的顶点可能会因为邻居或非邻居用完而不再正常；这些顶点也不能在输出中，所以像对待任何其他不正常的顶点一样对待它们并将它们也移除。继续下去，直到所有剩余的顶点都没有问题。

输出剩余顶点的集合。