398. Oliver and the Game

Oliver moves around an undirected connected graph with n vertices (0-indexed) and m edges. For each of q queries, given three distinct vertices a, b, c, determine whether c blocks every possible path from a to b - that is, whether every path between a and b passes through c. Print 'Yes' or 'No' for each query, one per line.

Input: The first line contains n, the number of vertices. The second line contains m, the number of edges. Each of the next m lines contains two integers, an undirected edge. This is followed by a line with q, the number of queries, then q lines each containing three integers a b c. Output: Print 'Yes' or 'No' for each query, one per line, indicating whether c lies on every path between a and b.

1 <= n <= 1000, 1 <= q <= 1000

This connects directly to the concept of 'cut vertices' (articulation points) from graph theory - c blocking every a-to-b path is a PAIR-SPECIFIC version of the more general 'is c a cut vertex for the WHOLE graph' question, checked here per query rather than globally.

For each query, check whether every path between two vertices must pass through a given third vertex. Brute force: Try to enumerate every possible path between a and b directly and check if all of them pass through c - this could be exponential in the number of paths for a densely connected graph, when a single removal-and-reachability check answers the question directly. Optimised: Since 'c blocks every path' is mathematically equivalent to 'removing c disconnects a from b', a SINGLE BFS/DFS after temporarily removing c directly answers each query - no need to enumerate or reason about paths explicitly at all, just check simple reachability in the modified graph.

For each query (a, b, c), remove vertex c and all of its incident edges from the graph entirely, then run a BFS or DFS from a to check whether b is still reachable. c blocks every a-b path exactly when a and b land in different components of this reduced graph, which is a direct implementation of the problem's definition, but it re-traverses the whole graph once per query. Time: O(q*(n+m)) Space: O(n+m)

Build the block-cut tree of the graph in a single DFS, where biconnected components and articulation points both become tree nodes connecting the blocks they belong to. A vertex c separates a and b exactly when c is an articulation point that lies on the unique path between a's and b's positions in this tree, a standard fact about block-cut trees. Root the tree and preprocess it for LCA queries (e.g., binary lifting); each query is then answered by testing, via ancestor checks against the LCA, whether c's tree node lies on the path between a's and b's tree nodes. Time: O((n+m) log n) Space: O(n+m)

First run Tarjan's articulation point algorithm once over the whole graph, a single DFS tracking discovery times and low-link values, to know up front which vertices are cut vertices at all. If c is not a cut vertex, it's structurally impossible for it to lie on every a-b path, so the query can be answered 'No' immediately without touching the graph. Only for queries where c actually is an articulation point does the algorithm fall back to removing c and checking connectivity via BFS/DFS, which prunes away most negative queries cheaply after one preprocessing pass. Time: O(n+m + q*(n+m)) Space: O(n+m)

1. Recognize that 'every path from a to b passes through c' is EXACTLY the definition of c being a CUT VERTEX separating a from b. 2. For each query, TEMPORARILY remove vertex c (skip it and every edge touching it), then run BFS/DFS from a. 3. If b is NO LONGER reachable, c was blocking every path; if b is still reachable, some path avoided c entirely.

Time: O(q * (n + m)) - each of the q queries requires one fresh BFS/DFS pass over the graph (minus the removed vertex). Space: O(n + m), for the graph representation and visited tracking, reused across queries.

Test c directly adjacent to a or b, a query where removing c doesn't disconnect a from b (expect 'No'), and q at its upper bound of 1000, which requires each query's check to be efficient.

Be ready to explain WHY doing a fresh removal-and-check per query (rather than trying to precompute something universal) is the right approach here - a vertex c that blocks paths between one specific pair (a,b) might NOT block paths between a different pair, so no single universal precomputation captures all query answers at once.