V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member Sign In
This topic created in 1701 days ago, the information mentioned may be changed or developed.
有几万个别名字典，存在如下情形： {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 Sep 3, 2021  1
并查集
|
 |
2
geelaw Sep 3, 2021 via iPhone 1
离线问题计算无向图的连通分量即可（比如 BFS ），在线问题用并查集。
|
 |
3
whusnoopy Sep 3, 2021 1
有一个问题细节待明确，别名集合好理解，在同一个联通子图里就好，别名的 key 怎么定？最短？首次出现？看样例里 B 并不是在 Bx 里第一次出现的
这个不管离线在线应该都是并查集更快，离线构建图的过程也是有时间空间开销的 |
|
5
whusnoopy Sep 3, 2021 1
@alex321
那这就是一个标准并查集的问题了，先便利一遍构建并查集，再便利一遍按并查集结果输出。针对你的样例写了段 Python 代码 https://gist.github.com/whusnoopy/c9b43dde396aa57f61318c09870d5517 |
Select Language