CSAcademy Round #63 : D. Graph Game

こちらはまぁまぁ良い出来でした。
https://csacademy.com/contest/round-63/task/graph-game/

問題

N頂点M辺の単純無向グラフが与えられる。
これを使い２人でターン制のゲームを行う。

自分のターンでは、次数が偶数の頂点を１つ選び、その頂点と辺を取り除く。
自分のターンでそのような頂点が選べなくなると終了である。
両者最適な順で頂点を選ぶ場合、勝者は先手後手どちらか。

解法

実はこれ辺の構成はどうでもよく、Nの偶奇で決まる。
次数が偶数である頂点数の偶奇は、全頂点数の偶奇に等しい。
１ターンで１個頂点が消えるため、次数が偶数の頂点の数もターン毎に偶奇反転する。

自ターンで次数が偶数の頂点の数が奇数の場合、常に１個はそのような頂点が選べるので負けはない。
よって初期状態でNが偶数なら後手、奇数なら先手必勝。

なお、「次数が偶数である頂点数の偶奇は、全頂点数の偶奇に等しい。」だが、全頂点の次数の和は当然ながら辺の数の２倍で偶数である。
よって次数が奇数となる頂点数は偶数となり、次数が偶数となる頂点はその残りということで全頂点の偶奇と一致する。

int T;
int N,M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		while(M--) cin>>x>>y;
		cout<<N%2<<endl;
	}
}

まとめ

なんというこけおどし問題。