b***y
发帖数: 2799 | 1 ☆─────────────────────────────────────☆
thrust (WoW 无限期冬眠中) 于 (Wed Jul 30 02:44:22 2008) 提到:
1B的A和B, 就是那天讨论过的.A做得很快, B则失败了.
我的思路没有问题, 但是很糟糕的是, 我在set merging上选了一个很愚昧的算法, 使
得large input速度极慢. 等我醒悟过来怎么回事, 8分钟早没了.
对于1~N的N个set的merge, 开一个长为N的数组, 如果x[n]=n, 则n是一个set的开头.
如果x[n]!=n, 则x[x[...x[n]...]](until find a head)是x[n]所属的set的开头.
直接按这个做就好了...反正最后只要数一数有几个set, 所以判断两个set是否同一个
才是最重要的--如果不同, 则把x1[n1]==n1改成x1[n1]=n2即可, 然后把count减1.
好久不做算法了, 手生了...
☆─────────────────────────────────────☆
Tevez99 (野兽99) |
|
