UTPC2012 : C - 森ですか？

続いて３問目。
ここらで結構難易度高い…。

http://utpc2012.contest.atcoder.jp/tasks/utpc2012_03

完全グラフからスタートして、辺を追加・削除する場合に森かどうかを答える問題。

N点の完全グラフの辺の本数はN*(N-1)/2、森を構成する最多辺数はN-1なので、辺の削除数MがM>=(N-1)(N-2)/2でないと森にはならない。
M<=100000なので、Nが450程度以上だと森は一切できない。

あとは指示通り辺を増減させて、辺がN-1本以下になった場合に、閉路の有無を調べればよい。
辺がN-1以下なのでO(N)程度で閉路判定できる。

int N,M;
int te;
int ne[500];
int edge[500][500];
int el[500][500];
int vis[500];

int dfs(int from,int cur) {
	int i;
	vis[cur]=1;
	FOR(i,ne[cur]) {
		int np = el[cur][i];
		if(np==from) continue;
		if(vis[np]) return 0;
		if(dfs(cur,np)==0) return 0;
	}
	return 1;
}

int isforest(){
	int i;
	ZERO(vis);
	FOR(i,N) {
		if(vis[i]==0 && ne[i]>=2) {
			if(dfs(-1,i)==0) return 0;
		}
	}
	return 1;
}

void addedge(int x,int y) {
	edge[x][y]=ne[x];
	el[x][ne[x]++]=y;
}
void deledge(int x,int y) {
	int p=edge[x][y];
	if(p<ne[x]-1) {
		int y=el[x][ne[x]-1];
		el[x][p]=y;
		edge[x][y]=p;
	}
	ne[x]--;
	edge[x][y]=-1;
}

void solve() {
	s64 res;
	s64 i,j;
	int x,y,l;
	
	N=GETi();
	M=GETi();
	
	if(N>450 || M<(N-1)*(N-2)/2-5) {
		FOR(i,M) {
			x=GETi();
			y=GETi();
			_P("no\n");
		}
		return;
	}
	
	FOR(x,N) {
		ne[x]=0;
		edge[x][x]=-1;
		FOR(y,N) if(x!=y) addedge(x,y);
	}
	te = N*(N-1)/2;
	
	FOR(i,M) {
		x=GETi()-1;
		y=GETi()-1;
		if(edge[x][y]==-1) {
			addedge(x,y);
			addedge(y,x);
			te++;
		}
		else {
			deledge(x,y);
			deledge(y,x);
			te--;
		}
		
		if(te>=N || !isforest()) {
			_P("no\n");
		}
		else {
			_P("yes\n");
		}
	}
}

まとめ

ここらへん、一発でAC取れてよかった。
すんなり回答が思いつけたのは練習の成果か。