読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 709 Div2 Med Permatchd2

問題概要

「グラフが "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);
            }
        }
    }
};