次のように条件を満たす全域木を構成することにします。

1. \(s_1s_2\ldots s_N\) で表される色に関する条件を満たす森を構成する。
2. 上記の森に辺を足して木にする。

\(2\) 番目は貪欲にやるなどすれば良いため、\(1\) 番目の手順が本質的です。

辺を以下の \(3\) 種類に分類します。
1. \(s_{a_i} = c_i\) かつ \(s_{b_i}=c_i\) の辺
2. \(s_{a_i} = c_i\) と\(s_{b_i}=c_i\)のうちちょうど一方を満たす辺
3. \(s_{a_i} \neq c_i\)かつ \(s_{b_i}\neq c_i\) の辺

\(1\) 番目の手順においては \(3\) 番目の種類の辺は役に立たないため、\(1, 2\) 番目の種類の辺のみを考えます。

\(1\) 番目の種類のうち何本かを閉路が出来ないように全域木の辺として選んだ時、\(2\) 番目の種類の辺で条件を満たす森が作れるかを考えます。選ばれた \(1\) 番目の種類の辺によって条件を満たした頂点の集合を \(X\) とした時、

• \(2\) 番目の種類の辺のうち条件を満たさない方の端点が \(X\) に含まれ、条件を満たす方の端点が \(X\) に含まれないような辺を全域木の辺として選び、条件を満たす方の端点を \(X\) に追加する。

という操作を繰り返して \(X = \{1,2,\ldots,N\}\) に出来るならば条件を満たす森が構成出来ています(上記操作で辺が選ばれる時、条件を満たす方の端点は孤立点なので閉路が出来ることはありません)。逆に、 \(X = \{1,2,\ldots,N\}\)でない状態で選べる辺が無くなった場合、そもそも指定された色の辺が存在しない頂点があるか、\(2\) 番目の種類の辺のみを考えた時の連結成分においてすべての頂点が条件を満たすには頂点数と同じだけ辺の本数が必要となり、必ず閉路が出来てしまう状態です。よって、上記の方法によって\(2\) 番目の種類の辺で条件を満たす森が作れるかどうかの判定及び構築が出来ます。
また、\(1\) 番目の種類の辺で \(X\) の要素数を増やしても不利になることはないため、\(1\) 番目の種類の辺は閉路が出来ない限りすべて選んだ場合のみを考えれば良いです。