Skip to main content

Practice · 5 of 5

Debug: The One-Shot Reachability

CHALLENGE
Difficulty: intermediate+25 XP

**Description:** The program answers q reachability queries on an undirected graph, but only the first query is ever right. Find and fix the bug. **Broken code:** ``cpp void solve(std::istream& in, std::ostream& out) { int n, m, q; in >> n >> m >> q; vector<vector<int>> adj(n + 1); for (int i = 0; i < m; ++i) { int u, v; in >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } vector<char> vis(n + 1, 0); for (int i = 0; i < q; ++i) { int a, b; in >> a >> b; vector<int> st{a}; vis[a] = 1; while (!st.empty()) { int u = st.back(); st.pop_back(); for (int v : adj[u]) if (!vis[v]) { vis[v] = 1; st.push_back(v); } } out << (vis[b] ? "YES" : "NO") << "\\n"; } } ` **Input:** Line 1: n m q (1 <= n <= 1000, 0 <= m <= 5000, 1 <= q <= 1000). Next m lines: u v. Next q lines: a b. **Output:** q lines: YES if b is reachable from a, else NO. **Example:** 3 1 2 / 1 2 / 1 2 / 2 3 -> YES / NO`.

Back to lesson: Practice: Debugging Problem Set