続いて3問目。
ここらで結構難易度高い…。
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取れてよかった。
すんなり回答が思いつけたのは練習の成果か。