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; }