TopCoder SRM 751 Div2 Hard HalfGraph

Div2とはいえ想像以上に本番の正答者が少ない。
https://community.topcoder.com/stat?c=problem_statement&pm=15295

問題

無向グラフが与えられる。
このグラフからいくつか辺を取り除き、各点の次数をちょうど半分にしたものが構築できるか。
できるならその例を示せ。

解法

1個辺を取り除くと、2つの頂点で次数が1ずつ、計2個減る。
よって、まず構築可否は以下の条件で判定できる。

• 各点の次数は偶数でなければならない。
• 各連結成分における各点の次数の総和は4の倍数でなければならない。

上記判定後、各連結成分に対して処理を行おう。
上記条件を満たしている場合、各連結成分の次数はすべて偶数なので、オイラー閉路を構築することができる。
またその時オイラー閉路は偶数長である。
よって、その閉路を構成する辺を１つおきに取り除けば、全頂点の次数を半減させることができる。

template<int MV> class UndirectedEulerPath {
public:
	vector<int> path;
	multiset<int> E[MV];
	void add_path(int x,int y) { E[x].insert(y); E[y].insert(x); }
	
	void dfs(int cur) {
		while(E[cur].size()) {
			int tar=*E[cur].begin();
			E[cur].erase(E[cur].begin());
			E[tar].erase(E[tar].find(cur));
			dfs(tar);
		}
		path.push_back(cur);
	}
	
	vector<int> GetPath(int root) {
		dfs(root);
		reverse(path.begin(),path.end());
		return path;
	}
};

class HalfGraph {
	public:
	
	vector <string> compute(vector <string> a) {
		UndirectedEulerPath<50> uep;
		int N=a.size();
		int i,j;
		int sum=0;
		FOR(i,N) {
			int num=0;
			FOR(j,N) if(a[i][j]=='1') {
				num++;
				if(i<j) uep.add_path(i,j);
			}
			if(num%2) return {};
			sum+=num;
		}
		if(sum%4) return {};
		
		FOR(i,N) if(uep.E[i].size()) {
			auto v=uep.GetPath(i);
			FOR(i,v.size()-1) if(i%2) a[v[i]][v[i+1]]=a[v[i+1]][v[i]]='0';
		}
		
		return a;
		
	}
}

まとめ

あれ、本当は連結成分毎に次数の和が４の倍数かチェックしないといけないのに全体が４の倍数かだけして通っちゃってる。
奇数長閉路が２つある場合とかダメなはずなんだけど、テストケースが甘いのかな。