Chokudai SpeedRun 002 K - 種類数 β

お題箱より。

K - 種類数 β

解法

この問題はグラフとして捉えると見通しが良くなります。それぞれの整数を頂点とし、ペア を頂点 と頂点 を結ぶ辺として考えます。整数を選ぶことを頂点に色を塗ることに喩えると、各辺ごとに「両端の頂点のうちどちらかを選んで色を塗る」という操作をして、最終的に色が塗られた頂点の数を最大にすればよいです。

このグラフで非連結な頂点（数字）同士は互いに関係しないので、それぞれの連結成分ごとに考えます。

連結成分に閉路がない場合

すなわち木になっている場合。このときは連結成分の頂点数 とすると辺数が 本であり、全ての頂点を選ぶことはできません。

ある1頂点 を諦めることにすると、各辺について から遠い方の頂点を選ぶことで必ず 個の頂点に色を塗ることができます。そのためこの連結成分によって答えに が加算されます。

連結成分に閉路がある場合

まず のような単純な閉路である場合を考えましょう。この場合は のように順繰りに選んでいくことで全ての頂点に色を塗ることができます。

そうとは限らない、どこかに閉路がある連結成分を考えます。このグラフの全ての頂点は、辺をいくつか選ぶことで

• ある1つの閉路
• その閉路内の頂点から木のように広がっていく部分たち

で覆うことができます。閉路が複数ある場合はいくつかの辺が無駄になりますが構いません。

このグラフで、まず閉路内の頂点を順繰りに選び、残りの辺で閉路から遠い方の頂点を選んでいくことで、全ての頂点に色を塗ることができます。

これで連結成分ごとに何個の頂点に色を塗れるかが分かるので、それらを合計すれば答えです。実装は座標圧縮＋Union-Findでできます。

ACコード

Submission #5577663 - Chokudai SpeedRun 002

シンプルな問題ですし、公式解説とほぼ同じですね。公式解説は辺に向きを付けて、辺が入っているほうの頂点（整数）を選ぶとみなす、と考えています。この記事では色を塗ると喩えてみました。お好きな方でどうぞ。