Submission #71556268

---

Source Code Expand

'''
方針: 逆向きのグラフ & BFS

例: 
1->2->3->4->5->6->7->8->9->10
4を黒く塗った場合、1,2,3,4が黒に到達可

メモ:
ある頂点を黒く塗った場合、そこへの辺が存在する頂点を求める 
-> 全て入力と逆向きの辺を追加したグラフで考えればよい(例では1<-2<-3<-4...<-9 というグラフを考えればよい)

1: 逆向きの有向辺を加える
2: 各クエリを実行する
 クエリ1: 頂点からBFS（ただし、すでに黒い点が現れたらそこで探索終了 -> 各頂点は高々1回程度の訪問）
 クエリ2: 頂点が黒へ到達可能か調べて解答

==== 
TLEの理由: 開始点がすでに黒の場合もBFSを開始している
-> 例えば、点1から10**5個の点への辺(逆向きの有向辺)があるケースで、クエリ「1 1」が10**5回きたら、各クエリ度に、頂点1の隣接頂点の訪問をしてしまう（10**5回）
-> 修正点: vがすでに黒に到達可能ならBFSしない
'''
from collections import deque
# BFS
def bfs(start, edges, visited):
  points = deque([start])
  visited[start] = True
  #reachable_black[start] = True
  while(len(points) > 0):
    p = points.popleft()
    # 隣接頂点を調べる
    for next_p in edges[p]:
      # 未訪問のみ調べる
      if(not visited[next_p]):
        visited[next_p] = True
        #reachable_black[next_p] = True
        points.append(next_p)
  return visited

# 入力
N,M = list(map(int, input().split()))
edges = [[] for _ in range(N+1)] # defaultdict->listに変更
for i in range(M):
  x,y = list(map(int, input().split()))
  edges[y].append(x) # 有向辺y->xの追加

# クエリ
Q = int(input())
visited = [False]*(N+1) # defaultdict->listに変更
#reachable_black = defaultdict(lambda:False) # わざわざvisitedと2つに分けることもなかった気がする
for i in range(Q):
  query_no,v = list(map(int, input().split()))
  # 黒へ到達可能な頂点を更新
  if(query_no == 1):
    # 黒へ到達可能な頂点の場合は探索skip
    if(visited[v]):
      continue
    visited = bfs(start=v, edges=edges, visited=visited)
  # 黒へ到達可能か(=BFSで訪問済みか)  
  elif(query_no == 2):
    if(visited[v]):
      print("Yes")
    else:
      print("No")

Submission Info

Judge Result