这是一个创建于 1203 天前的主题，其中的信息可能已经有所发展或是发生改变。
有几万个别名字典，存在如下情形： {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)}
目前我想到的办法很傻瓜，多重遍历。想请教下有什么高效的法子呢？
 |
1
RecursiveG 2021-09-03 03:09:16 +08:00  1
并查集
|
 |
2
geelaw 2021-09-03 04:30:38 +08:00 via iPhone 1
离线问题计算无向图的连通分量即可（比如 BFS ），在线问题用并查集。
|
 |
3
whusnoopy 2021-09-03 08:37:46 +08:00 1
有一个问题细节待明确，别名集合好理解，在同一个联通子图里就好，别名的 key 怎么定？最短？首次出现？看样例里 B 并不是在 Bx 里第一次出现的
这个不管离线在线应该都是并查集更快，离线构建图的过程也是有时间空间开销的 |
 |
4
alex321 OP |
|
5
whusnoopy 2021-09-03 11:09:58 +08:00 1
@alex321
那这就是一个标准并查集的问题了，先便利一遍构建并查集，再便利一遍按并查集结果输出。针对你的样例写了段 Python 代码 https://gist.github.com/whusnoopy/c9b43dde396aa57f61318c09870d5517 |
Select Language