在线BFS求不能离线图的最短路径

离线BFS就是先建图，然后在这个图上BFS，求最短路径之类的。

但如果点已经是n^5了，那边可能就非常多，事先建图，再BFS必然超时。

所谓在线BFS就是不需要建图，通过api逐渐bfs，可以要动态的消除图上的边。比如某些点已经访问过了，那遍历其它点时，如果有和访问过的点的边也不该访问，减少遍历时间。

参考

不预先建图，而是通过两个函数 setUsed 和 findUnused 来在线寻找边。其中数据是一个list，每个item是个点，点可能和其他有边。

• setUsed(u)：将 u 位置标记为已经访问过。
• findUnused(u): 找到和 u 邻接的一个未访问过的点。如果不存在, 返回None。

这个可以用python3的sortedcontainer解决，也可以用并查集。

• Sortedcontainer: index list。
  • setUsed = remove, findUnused = 二分查找
  • 代码模板
• 并查集。farther=parent，如果是负数，表示它是根，-2表示有两个点的集合，-3表示3个，2表示parent是2。
  • 参考
  • setUsed = union(u, u+1) 此时findUnused(u)就等于findUnused(u+1)了
  • 删除一段区间的，就是把这段元素都setUnsed.
  • findUnused(u) = 找个等于根的，不用O(n)遍历，因为setUsed给压缩加速这过程了。同时记录个left,right左边界和右边界
  • 代码模板
• 并查集比sortedcontainer更快
• 线段树也可以解决。区间更新，max树，区间里二分查找第一个大于等于x的节点。

在线BFS求最短路径模板，不需要visit，因为findUnused不会返回已经访问过的节点。

        dist = [INF] * n
        dist[p] = 0
        queue = deque([p])
        while queue:
            cur = queue.popleft()
            while True:
                next_ = findUnused(cur)
                if next_ is None:
                    break
                dist[next_] = dist[cur] + 1
                queue.append(next_)
                setUsed(next_)

时间复杂度 o(nlogn) n是节点数。如果离线bfs会o(n2)，假如每个点都有个边。

实际不用这么麻烦。直接裸写就行。参考

应用

• 2612. 最少翻转操作数 在线BFS
• 2617. 网格图中最少访问的格子数 DP+在线BFS求最短路径