\(B_i = \text{cond} [i \in X]\) とすると、以下がすべての \(i\) で成り立つことが条件です。

\[\displaystyle B_i \equiv \sum_{ j \in \text{adj}[i]} \text{cond} [B_j = B_i] \pmod 2\]

これは「 \(B_j = B_i\) 」と「同じ集合に属すること」が同値であることを考えれば明らかです。

上の式は

\[\displaystyle B_i \oplus \bigoplus_{ j \in \text{adj}[i]} \left( B_j \oplus B_i \oplus 1 \right)= 0\]

と考えることで \(\mathbb{F}_2\) の連立方程式と見ることができます。

解の存在判定および解の復元は、掃き出し法を用いて \(O(N^3 / w)\) でできます。本問題の制約は \(O(N^3)\) も許容します。

余談ですが、この問題はもしすべてが ? のとき解が存在することが保証されているそうです。