なんとか本番中に解けて良かった。
http://kcs.miz-miz.biz/contest/1027/view/E
問題
N頂点M無向辺のグラフがある。
各頂点は白か黒に塗られている。
ある白い頂点vについて、他の黒頂点群とvで閉路が作れるならvを黒くできる。
…という処理を出来るだけ黒頂点が増えるよう任意回数行った後、各頂点の色がどうなるか答えよ。
解法
想定解とは違う解法。
黒頂点についてUnion-Findで連結判定する。
次に白頂点について、隣接する黒頂点のうち、同一連結成分に属すものが2つ以上あるなら、閉路が生成できるのでその白頂点を黒にする、という処理を繰り返せば良い。
何度も白頂点を探索することによるTLEを防止するため、白頂点が黒頂点になった場合、その隣接白頂点から速めに探すようにした。
class UF { public: int um; vector<int> ufpar,ufrank,ufcnt; UF(int um_=201002) { um=um_; ufrank=vector<int>(um,0); ufcnt=vector<int>(um,1); for(int i=0;i<um;i++) ufpar.push_back(i);} int operator[](int x) {return (ufpar[x]==x)?(x):(ufpar[x] = operator[](ufpar[x]));} int count(int x) { return ufcnt[operator[](x)];} void unite(int x,int y) { x = operator[](x); y = operator[](y); if(x==y) return; if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x]; else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;} } }; int N,M,vis[201000],in[201000]; string S; vector<int> E[201000]; UF uf; set<int> cand; set<pair<int,int> > EE; void solve() { int i,j,k,l,x,y; string s; cin>>N>>S>>M; FOR(i,M) { cin>>x>>y; x--, y--; assert(x<y); if(EE.count(make_pair(x,y))) continue; EE.insert(make_pair(x,y)); E[x].push_back(y); E[y].push_back(x); in[x]++, in[y]++; if(S[x]=='B' && S[y]=='B') uf.unite(x,y); } FOR(i,N) if(S[i]=='W' && in[i]>1) cand.insert(i); int up=1; while(up) { up=0; queue<int> Q; ITR(it,cand) Q.push(*it); ZERO(vis); while(Q.size()) { int cur=Q.front(); Q.pop(); if(S[cur]=='B' || vis[cur]) continue; vis[cur]=1; map<int,int> MM; FORR(r,E[cur]) if(S[r]=='B') { if(++MM[uf[r]]>=2) { S[cur]='B'; cand.erase(cur); FORR(r2,E[cur]) if(S[r2]=='B') uf.unite(cur,r2); FORR(r2,E[cur]) if(S[r2]=='W' && in[r2]>1) vis[r2]=0, Q.push(r2); up++; break; } } } } cout<<S<<endl; }
まとめ
これも面白い問題でした。