ABland Yard [AtCoder Grand Contest 027 C]

https://beta.atcoder.jp/contests/agc027/tasks/agc027_c

前提知識

• 後退解析

考察過程

1. ab...にできるということは関連する全ての頂点からa,bの辺に遷移可能ということである
2. abへ遷移できない頂点を消すと、更にabへ遷移できない頂点が増える
3. どんどん消していって最終的にabへ遷移できる頂点が残ればそこからスタートすれば無限にab列を作れる

解法

https://beta.atcoder.jp/contests/agc027/submissions/3208481

abへ遷移できない頂点を消していって、最終的に頂点が残れば、abへ遷移できる頂点だけ残り、
どのように動かしても任意の文字列が作れることになる。
これを実現するために後退解析を用いよう。
　
ok[cu] := 頂点cuはabどちらへも遷移可能
acnt[cu] := 頂点cuから遷移可能なok[to]=1であり、文字aが書かれている頂点の数
bcnt[cu] := 頂点cuから遷移可能なok[to]=1であり、文字bが書かれている頂点の数
※ ちなみにcuはcurrent nodeという意味でcuとしてある
これを使う。
　
まずは全ての頂点cuについて、ok=1として、acnt,bcntを作ろう。
そのときにacntまたはbcntのどちらかが0の場合はok=0になるので、ok=0としてキューに入れる。
ng := ok=0となった頂点が入ってるキュー
　
キューが空になるまで ↔ 状態が確定（定常状態）しきるまで操作を続ける。
キューから1つ取り出し、その頂点につながっている頂点のacntまたはbcntを1つ減らす。
減らして、どちらかが0になれば、その頂点が新たにok=0になったことになるので、キューに入れる。
これを繰り返すことでok=0を伝搬させて、確定させることができる。
　
最後に1つでもok=1が残れば"Yes"
そうでないなら"No"

別解

AABBAABB...が無限に連なる列を構築可能かと問題と言い換えて、頂点倍化によって判定する解法もある。

int N, M; string S;
set<int> E[201010];
int ok[201010], acnt[201010], bcnt[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> S;
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].insert(b);
        E[b].insert(a);
    }
 
    rep(cu, 0, N) ok[cu] = 1;
 
    queue<int> ng;
    rep(cu, 0, N) {
        fore(to, E[cu]) {
            if (S[to] == 'A') acnt[cu]++;
            else bcnt[cu]++;
        }
        if (acnt[cu] == 0 or bcnt[cu] == 0) {
            ng.push(cu);
            ok[cu] = 0;
        }
    }
 
    while (!ng.empty()) {
        int cu = ng.front(); ng.pop();
 
        fore(to, E[cu]) if (ok[to]) {
            if (S[cu] == 'A') acnt[to]--;
            else bcnt[to]--;
 
            if (acnt[to] == 0 or bcnt[to] == 0) {
                ng.push(to);
                ok[to] = 0;
            }
        }
    }
 
    rep(cu, 0, N) if (ok[cu]) {
        printf("Yes\n");
        return;
    }
    
    printf("No\n");
}