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

[alex321]

有几万个别名字典，存在如下情形： {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)}

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

[RecursiveG]

并查集

[geelaw]

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

[whusnoopy]

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

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

[alex321]

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

[whusnoopy]

@alex321

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

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