AGC027 C 問題

pythonでやってる人が全然いない・・・。
トポロジカルソートよくわかんないけど、解けたから解説する。

AGC027のC問題

AtCoder Grand Contest 027のC問題です。
これ
C - ABland Yard

解説

公式の解説はこれ
https://img.atcoder.jp/agc027/editorial.pdf

’A'と’B'のうち、高々1種類しか隣接していない頂点を取り除いていく。

V = [ i for i in range(N)]

で頂点の個数を管理する。

Edges = [ set() for _ in range(N)]

で、各頂点に隣接する頂点を管理する。
同一の頂点を結ぶ辺は無視したいので、setで扱うことにする。

A = [ 0 for _ in range(N)]
B = [ 0 for _ in range(N)]

これで、各頂点に対し、隣接する'A'と'B'の個数を管理する。
ここで、同一の頂点を結ぶ辺は無視するものとする。
同一の頂点を結ぶ辺を無視するために今回はdefalutdictを用いた。便利。

’A'と’B'のうち、高々1種類しか隣接していない頂点を取り除いていくために、
まず、’A'と’B'のうち、高々1種類しか隣接していない頂点のsetをTとする。
そこから、BFSっぽいのかよくわからない、方法を使って、消していく。
これは公式の説明と同じで、高々1種類しか隣接していない頂点を帰納的に取り除いていく。
もし、全ての頂点が消えれば、目的のものは得られないことになり、解答は'No'になる。

'A'と’B'のうち、高々1種類しか隣接していない頂点がなくなるまでループを回す。
Tから1つ、頂点nを取り出して、それと隣接する頂点mと隣接するA'及び'B'の個数が1だけ減少する。
もし、頂点mが'A'と’B'のうち、高々1種類しか隣接していなければ、Tに追加する。

まとめると、次のプログラムになる。

from collections import defaultdict
N, M = map( int, input().split())
S = list( input())
E = [ list( map( int, input().split())) for _ in range(M)]
V = [ 1 for _ in range(N)]
Edges = [set() for _ in range(N)]
A = [0]*N
B = [0]*N
d = defaultdict(int)
for i in range(M):
    a, b = E[i]
    a, b = a-1, b-1
    a, b = min(a,b), max(a,b)
    Edges[a].add(b) #隣接する頂点をメモする
    Edges[b].add(a)
    if d[(a,b)] == 1:#(a,b)という辺を一度入力しれいれば、無視して次のループに進む。
        continue
    else:#一度目の入力をしたことをメモする。
        d[(a,b)] += 1
    if a == b:#ループ(同じ頂点を結ぶ辺)だと、このあとの方法だと、ダブルカウントしてしまうので、別扱い。
        if S[a] == 'A':
            A[a] += 1
        else:
            B[a] += 1
        continue
    if S[a] == 'A':
        A[b] += 1
    else:
        B[b] += 1
    if S[b] == 'B':
        B[a] += 1
    else:
        A[a] += 1
T = set()

for i in range(N):#'A'と’B'のうち、高々1種類しか隣接していない頂点をTに追加する。
    if A[i] == 0 or B[i] == 0:
        T.add(i)

while T:#'A'と’B'のうち、高々1種類しか隣接していない頂点がなくなるまでループを回す。
    n = T.pop()#一つ取り出す。
    V[n] = 0#'A'と’B'のうち、高々1種類しか隣接していない頂点なので、取り除く。
    for m in Edges[n]:#頂点nが消えると、それに隣接する頂点mに隣接する'A'及び'B'の個数が1だけ減少する。
        if V[m] == 1:
            if S[n] == 'A':
                A[m] -= 1
                if A[m] == 0:#隣接する頂点mに隣接する'A'及び'B'の個数が0になると、次に消える頂点になる。
                    T.add(m)
            else:
                B[m] -= 1
                if B[m] == 0:#隣接する頂点mに隣接する'A'及び'B'の個数が0になると、次に消える頂点になる。
                    T.add(m)
                
if sum(V) == 0:
    print('No')
else:
    print('Yes')
おまけ

オーダーはO(N+M)。