询问关于可撤销并查集
  • 板块学术版
  • 楼主Piggy343288
  • 当前回复18
  • 已保存回复18
  • 发布时间2023/7/14 09:00
  • 上次更新2023/11/3 09:59:06
查看原帖
询问关于可撤销并查集
762646
Piggy343288楼主2023/7/14 09:00

本人认为形如这样的做法是有问题的,Hack 考虑

merge(1,2),merge(2,3),merge(1,3)

现在 1,2,31,2,3 在同一连通块,然后我们 undone(opt[0])undone(opt[0]),此时因为后两个操作,1,2,31,2,3 应该依然联通,但根据这篇 Blog 应该会变成 1,31,3 不连通。

请问,是孩子对某处理解有误,还是可撤销并查集有更好的做法?

2023/7/14 09:00
加载中...