色を頂点とし、カードを辺としたグラフ \(G\) を考えます。 すると、もとの問題は次のように言い換えることが出来ます。

• \(G\) の各辺に対して、端点のうちどちらかを光らせることができる。光る頂点の個数の最大値は？

\(G\) の連結成分ごとに問題を解けば良いので、ある連結成分について考えます。

• 連結成分が木である場合、その頂点数を \(n\) とすると、 \(n-1\) 頂点を光らせることができます。実際、適当な頂点を根として根つき木を考え、各辺の子を光らせることで根以外の \(n-1\) 頂点が光ります。木であることから辺の本数は \(n-1\) なので、これより多く光らせることは不可能です。
• 連結成分が木でない場合、頂点数を \(n\) とすると、\(n\) 頂点全てを光らせることができます。実際、適当な全域木をとってきて、全域木として選ばれなかった辺 \(e\) の端点のうちひとつを根として木の場合と同じことをした後、根を \(e\) によって光らせれば良いです。

よって \(G\) の各連結成分に対し、木かそうでないか判定する問題になりました。これはDFS(深さ優先探索)などで \(G\) の頂点数、辺数に対して線形で解けます。