ビットセットを使用して \(O( \dfrac{nq}{\omega})\) でこの問題を解決しましたが、メモリの複雑さが \(O(\dfrac{n^2}{8})\) より大きいため、メモリ制限の下で渡すことはできません。 あるいは、\(O(qn)\) の各頂点の隣人を格納するだけの簡単な暴力的方法があります。 2つのソリューションを組み合わせるには、\(<m\) 隣接する各頂点にビットセットを格納し、各頂点に対して1つのベクトルを使用して隣接する \( \geq m\)を格納します。すると、時間複雑度は \(O(\dfrac{mq}{\omega}+q(n-m))\) となり、\(m = 8 \times 10^3\) を掛けると過ぎてしまいます。

リンクをコミットします。