询问不变的动态图连通性问题
  • 板块学术版
  • 楼主柳易辰
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/12/2 11:19
  • 上次更新2023/12/2 14:20:23
查看原帖
询问不变的动态图连通性问题
282929
柳易辰楼主2023/12/2 11:19

在无向动态图中,边集初始为空,点集大小为 nn。

钦定了两个节点 s,ts,t,动态图有增边、删边两种操作共 mm 个。每次询问 s,ts,t 是否联通,可离线。

此问题能否有复杂度低于 O(m2)O(m^2) 且比较简单的实现方式?

2023/12/2 11:19
加载中...