首页   注册   登录

wutiantong

V2EX 第 156258 号会员,加入于 2016-01-20 18:10:09 +08:00
今日活跃度排名 1979
wutiantong 最近回复了
10 小时 14 分钟前
回复了 Heiban 创建的主题 问与答 不会拒绝别人,太 sb 了。
确实 sb
本来没事,在这一问然后被老板看到开除了。
@lunar96 南京中华门城墙附近是有很多桂花树的,免费公园。
无锡没有桂树么?在南京生活倒是经常能闻到桂花香。
@inu1255
他这个算法额外引入了对元素顺序的依赖(从前向后遍历),仍然是一个 trivial 的贪心算法,不是最优解。
@ofooo 主体计算复杂度就是找出图的 conneted components。

在第 0 步中包含了一次这个计算,针对的是 N 个节点的图。

在最后一步中也包含了一次这个计算,针对的是 O(N*N) 个节点的图。
@ofooo 多项式量级。
@aijam 看我上一条的图解法,我觉得好像没问题了。
@wutiantong 我觉得我这个思路还可以抢救一下:

0. 首先我们要扩展补充 (complete) 所有(显式或隐含定义的)互斥二元组。
0-1. 比如说,假如给定(1, 2), (2, 3) 为互斥关系,那么(2, 3) 也是一个(隐含的)互斥关系。
0-2 从图的角度来说,任何两个元素只要有路径(path)连接,就应确保它们之间有一条直接的边(edge)。

1. 把(a, b) 二元组当作节点,其中 a 不等于 b,总共 n*(n-1)/2 个节点。

2. 在(a, b) 与 (b, c) 之间连线。

3. 从图中删掉所有(显式或隐含定义的)互斥二元组对应的节点。

4. 答案是剩余图的 connected component 个数。
关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2626 人在线   最高记录 5043   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.3 · 10ms · UTC 13:08 · PVG 21:08 · LAX 06:08 · JFK 09:08
♥ Do have faith in what you're doing.