给出圆上图的节点,找到要删除的最小数量的节点,以使图中的每个节点都具有到其下一个节点的边缘

问题描述 投票:1回答:2

给n个坐在桌旁的人,有些人彼此熟悉,熟悉度是双向关系,找到要从桌子上消除的最少人数,以便让桌子上的每个人都熟悉和它的邻居。给出O(n ^ 2)

的解

我目前的努力:如顺序所示,我尝试通过T(n)= T(n-1)+ O(n)解决问题,但是,如果我认为找到了包含m个节点的理想圆,现在我想添加一个新节点,则检查新节点是否可以成为该圆的新成员,并创建一个m + 1个节点的新圆,如果有可能然后解决问题,但如果不是,那么我确实需要存储长度为m-1,m-2,...的所有圆,并将这个新节点加到它们上,而这需要比O(n)多的时间时间。

algorithm
2个回答
2
投票

面对墙


0
投票

假设我们有一个具有n个节点(从0到n-1的图)

热门问题
推荐问题
最新问题