我不知道如何从这个问题开始:
一个图有 n 个顶点和 m 条边。没有两对顶点可以由多于一条边连接。Rahul 开始玩游戏: 他以下列方式改变边缘 -
- 他选择一个顶点,并从该顶点向不存在边的所有其他顶点添加一条边。
- 同时,从该顶点删除所有预先存在的边。
只有当每两个顶点之间存在一条直接边时,该游戏才会停止。你需要确定是否有可能完成这个游戏,或者这是否永远不会发生,无论他采取什么行动。
输入:将给出图形的初始状态。 输出:"is"或“否”
有人可以提示如何开始吗?
最佳答案
1) 移动顺序无关紧要(因为您可以交换任意两个后续移动以获得相同结果);
2) 相同顶点的两个后续变化具有零影响;
3)你可以到达最终状态iff。您最多可以更改任何顶点一次;
4) 任意两个相连的顶点都必须改变或都不变,任意两个不完全相连的顶点中的一个应该改变。
在图中取一个连通分量。那里的顶点应该全部改变或全部保持不变。如果组件未完全连接,则无法完成游戏。如果至少有三个连通分量,则不可能完成游戏。如果恰好有两个全连接分量,则应更改恰好其中一个分量中的所有顶点。
答案:当且仅当图形已经完全连接或由两个完全连接的组件组成时,游戏才能完成。 (很容易看出,当图由两个完全连接的组件组成时,更改顶点有效地将其从一个组件移动到另一个组件。)
检查答案的算法:假设给定了多个顶点 n,然后是 (a,b)
形式的边列表,其中 a
和 b
是 [1,n] 中的顶点编号。设 vertices
为记录数组 (num_edges, connected, sample)
,用 (0,k,k)
初始化(k
是顶点号)。然后对于每条边 (A,B):
- 将 A 和 B 的
num_edges
增加1
; - 如果
A.sample
等于B.sample
,转到下一条边; - 交换
A.connected
和B.connected
,从A.connected
顶点集合sample
到A.sample
并跟随connected
直到到达 B;到了下一个边缘。
最后检查所有从 1
开始并跟随 connected
的顶点是否具有相同的 num_edges
等于(它们的编号 - 1)和所有剩余的相似循环的顶点。时间应该是O(max(n log(n), m)),内存O(n)。
关于algorithm - 图论 : Will it stop or not?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42945512/