[AGC027] C - ABland Yard

[Q] https://atcoder.jp/contests/agc027/tasks/agc027_c

考察

・OKパターン
A-A
| |
B-B

・NGパターン1
A-A-B-B-A-A-B-B-...

かなりAB文字列を作れるけど、ループしていないのであれば、
"AABB" * 200000回 までしかループできず、有限。

・NGパターン2
A-B
| |
B-A
AからBBしかいけない。

1. 2つの条件を満たすグループが存在すればYes。
(a) ABどちらにも行ける頂点が、
(b) ループしている。
2. (a)を満たさない頂点への連結辺を全部eraseしちゃえばいい。dfsする。
3. 残ったグラフで"AABB"のループがあるか探索。dfsする。

実装

vector<ll> G[200020];
ll N, M;
string S, base = "AABB";

void debug() {
 rep(i, N) {
   if (G[i].empty()) continue;
   cerr << "G[" << i << "]:";
   for (auto v : G[i]) cerr << v << " ";
   cerr << endl;
 }
}

// ABどちらにも行ける頂点だけ残す
void dfs_erase(ll v) {
 ll dir = 0;
 for (auto u : G[v]) {
   dir |= (1 << (S[u] - 'A'));  // A=1, B=2
 }
 if (dir == 3 || dir == 0) return;
 queue<ll> Q;
 for (auto u : G[v]) {
   Q.push(u);
   auto it = lower_bound(all(G[u]), v);
   if (it != G[u].end()) G[u].erase(it);
 }
 G[v].clear();
 while (!Q.empty()) {
   dfs_erase(Q.front());
   Q.pop();
 }
}

// AABBでループするか確認
bool dfs_loop(ll v, ll d, vector<ll> &cnt) {
 if (base[d % 4] != S[v]) return false;
 chmin(cnt[v], d);
 if (d - cnt[v] > 4) return true;
 for (auto u : G[v]) {
   if (dfs_loop(u, d + 1, cnt)) return true;
 }
 return false;
}

int main() {
 cincout();

 cin >> N >> M >> S;
 rep(i, M) {
   ll a, b;
   cin >> a >> b;
   --a, --b;
   G[a].emplace_back(b);
   G[b].emplace_back(a);
 }
 rep(i, N) sort(all(G[i]));

 rep(i, N) dfs_erase(i);
 //  debug();
 bool ok = false;
 vector<ll> cnt(N, oo);
 rep(i, N) {
   ok = dfs_loop(i, 0, cnt);
   if (ok) break;
 }
 if (ok)
   cout << "Yes" << endl;
 else
   cout << "No" << endl;
}

https://atcoder.jp/contests/agc027/submissions/30961888