补图最短路
已知一张无向无权稀疏图 \(G=(V,E)\)，定义其补图 \(G=(V,E')\)，其中 \(E'=\{(u,v)\mid(u,v)\notin E\}\)。\(n,m\le 10^6\)。求结点 \(s\) 在补图上到每个结点的最短路。
若直接跑最短路时间复杂度为退化到 \(O(n^2)\)，无法通过。
可以发现主要时间消耗在了扫描大量的邻居上，那么我们就可以维护未被访问过的结点集合 \(S\)，每次排除掉原图上的邻居后在 \(S\) 中在 \(S\) 中找点，这样子时间复杂度将为 \(O(n+m)\)。