TopCoder SRM 709 Div2 Med Permatchd2

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14539

問題概要

「グラフが "pretty" である」を，「グラフに含まれる任意の連結成分 S に対して，|E(S)| が偶数である」と定義する．
ここで，単純グラフが1つ与えられる．このグラフを "pretty" なものにするためには，辺を最小で何本追加すればよいか求めよ．
どのようにしても "pretty" にできない場合は，-1 とせよ．

・制約
1 <= |V(G)| <= 50
G は単純グラフである．

解法

まず，各連結成分に対して，頂点数と辺数を求めておく．これはDFSで十分．
偶数のものはそのままでよいので，奇数のものについて考える．
まず，|E(S)| が奇数となる連結成分 S の中に，辺を追加できるならそれが最適であることは明らかである．
よって，それが可能であるなら前もって追加して，偶数の連結成分にしておく．以下はそれを前提とする．
S の中に辺を追加できないのは，S が完全グラフである場合である．
残った奇数の連結成分（すべて完全グラフ）は，それらを環状に結べば全体として偶数にできる．
1つしか残らなかった場合は，偶数の連結成分と一本の辺を追加して結べば良い．
1つしか残らず，かつ偶数の連結成分が0個だった場合は，どうやっても無理なので -1 を返す．

ソースコード

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Permatchd2 {
public:
    int fix(vector<string> graph) {
        vector<bool> used(graph.size());
        vector<pair<int, int>> v;
        for(int i=0; i<graph.size(); ++i) {
            if(!used[i]) {
                int v_cnt = 0, e_cnt = 0;
                dfs(graph, i, v_cnt, e_cnt, used);
                e_cnt /= 2;
                v.push_back(make_pair(v_cnt, e_cnt));
            }
        }
        int res = 0;
        int odd_num = 0;
        for(int i=0; i<v.size(); ++i) {
            int v_cnt = v[i].first, e_cnt = v[i].second;
            if(v_cnt*(v_cnt-1)/2 != e_cnt && e_cnt % 2 == 1) {
                res++;
                v[i].second += 1;
            }
            odd_num += v[i].second % 2 == 1;
        }
        if(odd_num == 1) {
            res = -1;
        } else {
            res += odd_num;
        }
        return res;
    }
    void dfs(vector<string> const& g, int v, int& v_cnt, int& e_cnt, vector<bool>& used) {
        used[v] = true;
        v_cnt += 1;
        e_cnt += count(g[v].begin(), g[v].end(), 'Y');
        for(int i=0; i<g[v].size(); ++i) {
            if(used[i]) {
                continue;
            }
            if(g[v][i] == 'Y') {
                dfs(g, i, v_cnt, e_cnt, used);
            }
        }
    }
};