ABC435Dを解いた【BFS】

筆者はレート800前後の茶～緑コーダ

ABC435当日にACできなかったD問題を解いていく

実装コード

ノードを新しく黒塗りしたら
片方向グラフの逆方向からBFSして
探索したノードも黒色とみなす。

あとは聞かれたノードが黒色とみなせるか判定すればOK

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    N, M = rLI()

    blk = set()
    
    G = defaultdict(list)
    H = defaultdict(list)
    
    for _ in range(M):
        a, b = rLI()
        G[a].append(b)
        H[b].append(a)
    

    Q = rI()
    for _ in range(Q):
        q, v = rLI()
        if q == 1:
            u = deque([v])
            while u:
                cur = u.popleft()
                if cur in blk:
                    continue
                blk.add(cur)
                for nxt in H[cur]:
                    if nxt not in blk:
                        u.append(nxt)
        if q == 2:
            ans = v in blk
            print('Yes' if ans else 'No')
    
if __name__ == '__main__':
    main()

感想

幅優先探索の範囲を狭める発想はなかった