2018 ICPC Asia Jakarta Regional Contest K問題 "Boomerangs"
問題概要
N頂点M辺の無向単純グラフが与えられる。2本の辺からなる集合であり、その2辺が1つの頂点を共有しているものをブーメランと呼ぶ。ブーメランの集合であり、互いに素である、すなわちそれに含まれるどの2つのブーメランも辺を共有しないようなもののうち、要素数が最大であるものを1つ求めよ。
1<=N,M<=10^5
解法
各連結成分について以下を行います。
まず初めにすべての辺に適当に向きをつけ、各頂点の出次数を数えてみます。
連結な2頂点で出次数がどちらも奇数のとき、間の辺の向きを逆にすることでどちらも出次数を偶数にできます。
連結な2頂点で出次数が一方だけ奇数のとき、同様に向きを逆にして偶奇を入れ替えることができます。
そこで、グラフ上でDFSをして、行きがけと帰りがけの両方で頂点を見ていき、今訪れている頂点が奇数ならばその次に訪れる頂点との辺の向きを逆にすることを繰り返せば、出次数が奇数である頂点が高々1個(あるとしたらDFSの始点/終点)であるようにできます。
その後、各頂点について、そこから出ていく辺のうち2つを選んでブーメランを作っていくと、[連結成分内の辺数]/2個(切り捨て)のブーメランを作ることができ、これが最適になります。
