algorithm - 图论 : Will it stop or not?

Question

我不知道如何从这个问题开始:

一个图有 n 个顶点和 m 条边。没有两对顶点可以由多于一条边连接。Rahul 开始玩游戏:他以下列方式改变边缘 -

• 他选择一个顶点，并从该顶点向不存在边的所有其他顶点添加一条边。
• 同时，从该顶点删除所有预先存在的边。

只有当每两个顶点之间存在一条直接边时，该游戏才会停止。你需要确定是否有可能完成这个游戏，或者这是否永远不会发生，无论他采取什么行动。

输入:将给出图形的初始状态。输出:"is"或“否”

有人可以提示如何开始吗？

Answer 1

1) 移动顺序无关紧要(因为您可以交换任意两个后续移动以获得相同结果)；
2) 相同顶点的两个后续变化具有零影响；
3)你可以到达最终状态iff。您最多可以更改任何顶点一次；
4) 任意两个相连的顶点都必须改变或都不变，任意两个不完全相连的顶点中的一个应该改变。

在图中取一个连通分量。那里的顶点应该全部改变或全部保持不变。如果组件未完全连接，则无法完成游戏。如果至少有三个连通分量，则不可能完成游戏。如果恰好有两个全连接分量，则应更改恰好其中一个分量中的所有顶点。

答案:当且仅当图形已经完全连接或由两个完全连接的组件组成时，游戏才能完成。 (很容易看出，当图由两个完全连接的组件组成时，更改顶点有效地将其从一个组件移动到另一个组件。)

检查答案的算法:假设给定了多个顶点 n，然后是 (a,b) 形式的边列表，其中 a 和 b 是 [1,n] 中的顶点编号。设 vertices 为记录数组 (num_edges, connected, sample)，用 (0,k,k) 初始化(k 是顶点号)。然后对于每条边 (A,B):

1. 将 A 和 B 的 num_edges 增加 1；
2. 如果A.sample等于B.sample，转到下一条边；
3. 交换A.connected和B.connected，从A.connected顶点集合sample到A.sample 并跟随 connected 直到到达 B；到了下一个边缘。

最后检查所有从 1 开始并跟随 connected 的顶点是否具有相同的 num_edges 等于(它们的编号 - 1)和所有剩余的相似循环的顶点。时间应该是O(max(n log(n), m))，内存O(n)。