Yosupo Wettbewerb E: Oh, Vertexes & Edges!

AtCoder Grand Contest 014E: Blue and Red Tree - omochan's diary

これと全く同じじゃん!と思ったけど微妙に違った。

最初辺に注目してマージテクしようと思ったが(つまりqueueに入れるのを辺にした)、これでは新たに両端が黒になった辺がqueueに入れられることはない。入出力5を見てみるとわかると思う。

なのでqueueに入れるのは新たにmergeされた点で、元のグラフで隣接している点が黒のものがあったらmergeするというのを繰り返す。

queue<int> que;
bool B[MAX_N];

struct UF {
	int par[MAX_N];
	set<int> E[MAX_N]; //edge

	int find(int x) {
		if(par[x] == x) return x;
		else return par[x] = find(par[x]);
	}

	void init(int n) {
		rep(i, 0, n) par[i] = i;
	}

	void unite(int a, int b) { //update and merge
		a = find(a);
		b = find(b);
		if(a == b) return;
		par[a] = b;
		if((int)E[a].size() > (int)E[b].size()) swap(E[a], E[b]);
		for(int w: E[a]) {
			if(E[b].count(w)) que.push(w);
			E[b].insert(w);
		}
		E[a].clear();
	}
};

int N, M;

UF U;
vector<int> E[MAX_N];

void solve() {
	cin >> N;
	string str; cin >> str;
	rep(i, 0, N) {
		if(str[i] == 'B') {
			que.push(i);
		}
	}
	U.init(N);
	cin >> M;
	rep(i, 0, M) {
		int a, b;
		cin >> a >> b; a--; b--;
		E[a].pb(b);
		E[b].pb(a);
		U.E[a].insert(b);
		U.E[b].insert(a);
	}
	while(!que.empty()) {
		int v = que.front(); que.pop();
		if(B[v]) continue;
		B[v] = true;
		for(int w: E[v]) {
			if(B[w]) U.unite(w, v);
		}
	}
	rep(i, 0, N) {
		if(B[i]) cout << "B";
		else cout << "W";
	}
	cout << "\n";
}

テストケース何個か試したけどあってるっぽいから多分あってる(適当)