題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 ABC435D Reachability Query 2

rating: 644

Problem Statement

題目簡述

給定一個 $N$ 個節點、 $M$ 條邊的有向圖，初始所有節點為白色。
處理 $Q$ 個查詢：

1 v：將節點 $v$ 染成黑色。
2 v：判斷從節點 $v$ 出發，沿著邊走，是否能到達某個黑色節點。

Constraints

約束條件

$1 \le N, M, Q \le 3 \times 10^5$
無自環、無重邊

思路：反向圖 + BFS/DFS 預處理

關鍵轉換

將「從 $v$ 能否到達黑點」轉換為「黑點能否沿反向邊到達 $v$ 」。

觀察：直接對每個查詢 2 進行 BFS/DFS 會 TLE。但如果我們反向思考：

建立反向圖 $G'$ ：原圖中 $u \to v$ 的邊，在反向圖中變成 $v \to u$ 。
當節點 $v$ 被染黑時，從 $v$ 在反向圖上進行 BFS，標記所有能到達的節點為「可達黑點」。
查詢時，直接判斷該節點是否已被標記。

為何正確？

在原圖中「 $u$ 能到達 $v$ 」 $\Leftrightarrow$ 在反向圖中「 $v$ 能到達 $u$ 」。
因此，當 $v$ 變黑時，在反向圖上從 $v$ 出發能到達的所有節點，都是原圖中能到達 $v$ （黑點）的節點。

優化：每個節點最多被標記一次，總體 BFS 的節點訪問次數為 $O(N)$ ，邊訪問次數為 $O(M)$ 。

複雜度分析

時間複雜度： $\mathcal{O}(N + M + Q)$
空間複雜度： $\mathcal{O}(N + M)$

Code

from collections import deque

def solve():
    n, m = map(int, input().split())

    rg = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(lambda x: int(x) - 1, input().split())
        rg[v].append(u)

    vis = set[int]()
    q = int(input())

    for _ in range(q):
        op, v = map(int, input().split())
        v -= 1
        if op == 1:
            q = deque([v] if v not in vis else [])
            while q:
                u = q.popleft()
                vis.add(u)
                for v in rg[u]:
                    if v not in vis:
                        q.append(v)
        else:
            print("Yes" if v in vis else "No")

if __name__ == "__main__":
    solve()