Yosupo Wettbewerb : E : Oh, Vertexes & Edges!

なんとか本番中に解けて良かった。
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;
}

まとめ

これも面白い問題でした。