AtCoder ARC #205 : B - Triangle Toggle

全完できたけど、色々手間取った。
https://atcoder.jp/contests/arc205/tasks/arc205_b

問題

N点の完全無向グラフがある。
うち指定されたM辺は黒、残りの辺は白で塗られている。

ここで、閉路を成す3辺を選び、白黒反転できるとする。
黒辺の数の最大値を求めよ。

解法

この処理を繰り返すと、結局任意の閉路に沿って白黒反転できる。
これはつまり、各点における黒辺・白辺の次数は2ずつなら任意に増減できる。

そこで、各点の黒辺の数を偶奇を保った範囲で増加させればよい。

int N,M;
int E[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) E[i]=N-1;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1]--;
		E[y-1]--;
	}
	ll sum=0;
	FOR(i,N) {
		if(E[i]%2) E[i]--;
		sum+=E[i];
	}
	cout<<sum/2+M<<endl;
	
}

まとめ

ちょっと手間取ってしまった。
今見たらもっとあっさり解けそうね。