比较复杂的别名字典去重优化

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1189 天前的主题，其中的信息可能已经有所发展或是发生改变。

有几万个别名字典，存在如下情形： {A:A1} {A1:A2} {A3:A4} {A2:A3} {B4:B3} {B1:B4} {B4:B} {B3:B2} {B2:B5}

想构造出如下结果： {A:(A1,A2,A3,A4)} {B:(B1,B2,B3,B4,B5)}

目前我想到的办法很傻瓜，多重遍历。想请教下有什么高效的法子呢？

5 条回复 • 2021-09-03 11:09:58 +08:00

RecursiveG

2021-09-03 03:09:16 +08:00

并查集

geelaw

2021-09-03 04:30:38 +08:00 via iPhone

离线问题计算无向图的连通分量即可（比如 BFS ），在线问题用并查集。

whusnoopy

2021-09-03 08:37:46 +08:00

有一个问题细节待明确，别名集合好理解，在同一个联通子图里就好，别名的 key 怎么定？最短？首次出现？看样例里 B 并不是在 Bx 里第一次出现的

这个不管离线在线应该都是并查集更快，离线构建图的过程也是有时间空间开销的

alex321

2021-09-03 09:56:12 +08:00

@whusnoopy #3 key 可以不定。给集合元组也可以的。
(A,A1,A2,A3,A4)
(B,B1,B2,B3,B4,B5)

whusnoopy

2021-09-03 11:09:58 +08:00

@alex321

那这就是一个标准并查集的问题了，先便利一遍构建并查集，再便利一遍按并查集结果输出。针对你的样例写了段 Python 代码

https://gist.github.com/whusnoopy/c9b43dde396aa57f61318c09870d5517