AGC027 C - ABland Yard

問題

各頂点にAかBと書かれた無向グラフが与えられる
好きな頂点から始めて辺を辿って移動し、通った頂点に書かれた文字を順に並べて文字列を作る
このとき文字A、Bのみからなる任意の文字列が作れるかどうかを判定

2 <= 頂点数n <= 2*10^5
1 <= 辺数m <= 2*10^5

解法

グラフが条件を満たすとき、ある頂点から"Aが書かれた頂点"にも"Bが書かれた頂点"にも行けて、そのどちらについても同様になる
これは例えば-A-A-B-B-(左端と右端は繋がってる)という閉路があれば成り立つ
(-A-A-B-B-A-A-B-B-...と複数回繋げたような閉路でも全て成り立つ)
ゆえにそういう閉路を検出する問題と言い換えられる
(以下これを良い閉路と呼びます)

良い閉路を検出するにはどうするか?
トポロジカルソート(Kahnのアルゴリズム)の要領で、「辺で結ばれている頂点たちに書かれた文字が1種類(または0種類)しかない」ような頂点を順に消していけばいい
最終的に全ての頂点が消えたら良い閉路は存在せず、頂点が残ったら存在する

実装

a[v], b[v] : 頂点vに直接繋がっている点のうちA[B]と書かれた頂点の個数

頂点を消すとき同時に辺も消さないといけないから、辺の情報はvectorじゃなくsetを使う

int n, m, x, y, a[200200], b[200200], v;
string s;
set<int> e[200200], q;

signed main() {
	cin >> n >> m >> s;
	v = n;
	rep(i,m) {
		cin >> x >> y;
		x--, y--;
		e[x].insert(y), e[y].insert(x);
	}
	rep(i,n) {
		each(j,e[i]) (s[j]=='A' ? a : b)[i]++;
		if (a[i]==0 || b[i]==0) q.insert(i);
	}
	while (!q.empty()) {
		int u = *q.begin(); q.erase(q.begin());
		v--;
		each(i,e[u]) if (i!=u) {
			e[i].erase(u);
			(s[u]=='A' ? a : b)[i]--;
			if (a[i]==0 || b[i]==0) q.insert(i);
		}
	}
	cout << (v ? "Yes" : "No") << endl;
}