AtCoder ARC #099 : E - Independence

この回は不参加だけど、これは自力で解けたかな。
https://arc099.contest.atcoder.jp/tasks/arc099_c

問題

N頂点M辺の無向グラフが与えられる。
このグラフを２つの完全グラフに分けることができるか。
できるとき、両グラフ内の辺の総数の最小値を求めよ。

解法

あり得る両完全グラフのサイズの組み合わせがわかれば、そのうち辺の総数が最小なものを求めればよい。

元のグラフの補グラフを考える。
元グラフが２つの完全グラフになるということは、同じ側の完全グラフに入る頂点間は、補グラフで辺があってはならない。

そこで、補グラフの各連結成分を考えよう。
条件より連結成分は二部グラフでなければならず、奇閉路がある場合解なしである。
二部グラフである場合、それぞれの頂点数をa,bとすると、どちらかを最終的な完全グラフの前者、後者に割り振ることになる。
これはDPの要領で両方を試せばよい。

int N,M;
int C[700][700];
vector<int> E[707];
int vis[707];
int cnt[2];
int ok[707][707];

void dfs(int cur,int c) {
	if(vis[cur]!=-1) {
		if(vis[cur]==c) return;
		cout<<"-1"<<endl;
		exit(0);
		return;
	}
	cnt[c]++;
	vis[cur]=c;
	FORR(e,E[cur]) dfs(e,c^1);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		C[x-1][y-1]=C[y-1][x-1]=1;
	}
	FOR(x,N) {
		C[x][x]=1;
		FOR(y,N) if(C[x][y]==0) E[x].push_back(y);
	}
	
	
	ok[0][0]=1;
	int sum=0;
	MINUS(vis);
	FOR(i,N) if(vis[i]==-1) {
		cnt[0]=cnt[1]=0;
		dfs(i,0);
		
		FOR(x,sum+1) if(ok[x][sum-x]) {
			ok[x+cnt[0]][sum-x+cnt[1]]=1;
			ok[x+cnt[1]][sum-x+cnt[0]]=1;
		}
		
		sum+=cnt[0]+cnt[1];
	}
	
	int mi=1<<30;
	FOR(x,N+1) if(ok[x][N-x]) mi=min(mi,x*(x-1)/2+(N-x)*(N-x-1)/2);
	cout<<mi<<endl;
	
}

まとめ

これは気持ちよく解けて良かった。