グラフ \(G(V,E)\) の補グラフにおける、頂点 \(s\ (=0)\) から各頂点 \(v\) までの最短距離 \(\mathtt{dist}(v)\) の列挙を \(O(\lvert V\rvert + \lvert E\rvert)\) 時間で行う方法を説明します。

方針は公式解説と概ね同じです。

頂点 \(v\) に隣接する頂点の集合を \(N(v)\) とします。各頂点 \(v\) に対する \(N(v)\) の計算は \(O(\lvert V\rvert + \lvert E\rvert)\) 時間で行えます。

次の擬似コードのように各頂点 \(v\) に対する \(\mathtt{dist}(v)\) を列挙します。赤字の部分が公式解説からの変更点であり、重要なのは、現在見ている頂点に隣接しているかどうかを表すフラグを管理する配列 \(\mathtt{mark}\) を持って適切に更新することです。

1. \(\quad\)\(\mathtt{//}\) 最短距離の暫定値
2. \(\quad\)\(\mathtt{dist}(s)\gets 0\)
3. \(\quad\)\(\mathtt{for}\ v\in V\setminus\lbrace s\rbrace\colon\)
4. \(\quad\quad\)\(\mathtt{dist}(v)\gets \infty\)
6. \(\quad\)\(\mathtt{//}\) 公式解説の \(L\)
7. \(\quad\)\(L\gets \mathtt{list}(V\setminus\lbrace s\rbrace)\) \(\mathtt{//}\) \(V\setminus\lbrace s\rbrace\) の要素からなる list (順不同)
9. \(\quad\)\(\mathtt{//}\) \(\textcolor{red}{\mathtt{mark}(v)}\colon\) 頂点 \(v\) が現在見ている頂点に隣接しているかどうかを表すフラグ
10. \(\quad\)\(\textcolor{red}{\mathtt{for}\ v\in V\colon}\)
11. \(\quad\quad\)\(\textcolor{red}{\mathtt{mark}(v)\gets \mathtt{false}}\)
13. \(\quad\)\(\mathtt{//}\) BFS に用いる Queue
14. \(\quad\)\(Q\gets \mathtt{deque}(\lbrace s\rbrace)\)\(\quad\mathtt{//}\) \(s\) のみからなる \(\mathtt{deque}\)
15. \(\quad\)\(\mathtt{while}\ \lvert Q\rvert\gt 0\colon\)
16. \(\quad\quad\)\(\mathtt{//}\) 現在見ている頂点
17. \(\quad\quad\)\(u\gets Q.\mathtt{pop\_front}()\)
19. \(\quad\quad\)\(\mathtt{//}\) \(u\) に隣接している頂点に対して隣接フラグを立てる
20. \(\quad\quad\)\(\mathtt{//}\) 各頂点は高々 \(1\) 回ずつしか見られないので、ここの \(\mathtt{for}\) は全体で高々 \(2\lvert E\rvert\) 回しか回らない
21. \(\quad\quad\)\(\textcolor{red}{\mathtt{for}\ v\in N(u)\colon}\)
22. \(\quad\quad\quad\)\(\textcolor{red}{\mathtt{mark}(v)\gets \mathtt{true}}\)
24. \(\quad\quad\)\(\mathtt{//}\) \(L\cap N(u)\)
25. \(\quad\quad\)\(L'\gets \mathtt{empty\_list}()\)
26. \(\quad\quad\)\(\mathtt{for}\ v\in L\colon\)
27. \(\quad\quad\quad\)\(\mathtt{//}\) 計算量改善ポイント: 平衡二分探索木に対する membership クエリを配列アクセスで代替
28. \(\quad\quad\quad\)\(\mathtt{if}\ \textcolor{red}{\mathtt{mark}(v)}\colon\)
29. \(\quad\quad\quad\quad\)\(\mathtt{//}\) \(\mathtt{mark}(v)\iff v\in N(u)\)
30. \(\quad\quad\quad\quad\)\(L'.\mathtt{append}(v)\)
31. \(\quad\quad\quad\)\(\mathtt{else}\colon\)
32. \(\quad\quad\quad\quad\)\(\mathtt{//}\) \(v\notin N(u)\) であり、つまり \(v\) は \(G\) の補グラフにおいて \(u\) と隣接している
33. \(\quad\quad\quad\quad\)\(\mathtt{dist}(v)\gets\mathtt{dist}(u)+1\)
34. \(\quad\quad\quad\quad\)\(Q.\mathtt{push\_back}(v)\)
35. \(\quad\quad\)\(\mathtt{//}\) \(L\) の更新
36. \(\quad\quad\)\(L\gets L'\)
38. \(\quad\quad\)\(\mathtt{//}\) \(u\) に隣接している頂点に対して立てた隣接フラグを下ろす (この操作によって全ての頂点 \(v\) について \(\mathtt{mark}(v)\) は \(\mathtt{false}\) となる)
39. \(\quad\quad\)\(\textcolor{red}{\mathtt{for}\ v\in N(u)\colon}\)
40. \(\quad\quad\quad\)\(\textcolor{red}{\mathtt{mark}(v)\gets \mathtt{false}}\)

各変数に対して適切なデータ構造を用いることで、この手続きは \(O(\lvert V\rvert + \lvert E\rvert)\) 時間となります。

実装例 (C++ 20 (gcc 12.2))