\(c_{a_i} \neq c_{b_i}\) の辺については向きを簡単に決めることが出来ます。

\(c_{a_i} = c_{b_i}\) の辺については、\(a_i, b_i\) の到達可能な頂点数が等しいので、\(a_i\) と \(b_i\) は相互に到達可能でないといけない、つまり強連結でないといけないです。

以上の考察より、この問題は「連結な無向グラフが与えられるので、辺に向きづけして全体を強連結にする」問題へ帰着できます。

実際に、「dfs木を作り、木に含まれる辺は全て根から離れる方向、含まれない辺(後退辺)は全て根に近づく方向に向きづけする」ことで題意を満たすことができます。証明のポイントは次の2つです。

• グラフに橋が存在しないことを示す
• lowlinkに注目することでどの頂点からも根に到達できることを示す

想定解の計算量は、「解が存在する」制約の元で \(O(N + M)\)、この制約がない場合 \(O(N + M + \frac{N(N + M)}{\sigma})(\sigma: \mathrm{wordsize})\)です。