Graph bug hunt

Questions 1 to 5 of 8

1. 1. A teammate wrote this function to store a directed graph, where an edge a to b means you can go from a to b only: ``cpp Graph build(int n, const std::vector<std::pair<int, int>>& edges) { Graph g(n); for (auto [a, b] : edges) { g[a].push_back(b); g[b].push_back(a); } return g; } `` What is the bug?

   The edge from a to b is never stored, so no node has an outgoing edge.It also stores the reverse edge from b to a, so the graph acts as undirected and the search follows edges that do not exist.push_back cannot be used on a vector of vectors, so the graph is always empty.The loop needs a visited array, otherwise it runs forever.
2. 2. What does this program print? ``cpp Graph g = build(4, {{0, 1}, {0, 2}, {1, 3}, {2, 3}}); for (int x : reachableFrom(g, 0)) std::cout << x << ' '; ` Here build stores only the given directed edges, and reachableFrom is the explicit-stack search from Lab 3 that marks a node when it is pushed. `cpp std::vector<int> reachableFrom(const Graph& g, int start) { std::vector<bool> seen(g.size(), false); std::stack<int> todo; todo.push(start); seen[start] = true; std::vector<int> order; while (!todo.empty()) { int u = todo.top(); todo.pop(); order.push_back(u); for (int v : g[u]) { if (!seen[v]) { seen[v] = true; todo.push(v); } } } return order; } ``

   0 1 2 30 1 3 20 2 1 30 2 3 1
3. 3. In the Lab 4 test table, which is the smallest number of nodes where the recursive DFS on a path crashed with exit code 139?

   10,00050,000100,0001,000,000
4. 4. This recursive search is meant to count the nodes reachable from node 0. It crashes on the graph below. ``cpp void dfs(const Graph& g, int u, int& count) { ++count; for (int v : g[u]) { dfs(g, v, count); } } int main() { Graph g = {{1}, {0}}; // 0 -> 1 -> 0 int count = 0; dfs(g, 0, count); std::cout << "reachable: " << count << '\n'; } `` What happens when it runs?

   It never stops: node 0 calls node 1, node 1 calls node 0, and the calls repeat until the call stack runs out, so the program crashes with exit code 139.It prints reachable: 2 and exits with code 0, because each node is counted once.It prints reachable: 1, because the loop stops at the first node it has already counted.It fails to compile, because count is passed by reference into a recursive function.
5. 5. This BFS is meant to visit every node once, but node 3 is popped twice on a real run. Here the mark is set when a node is popped. ``cpp Graph g = {{1, 2}, {3}, {3}, {}}; std::vector<bool> seen(g.size(), false); std::queue<int> q; q.push(0); seen[0] = true; while (!q.empty()) { int u = q.front(); q.pop(); seen[u] = true; for (int v : g[u]) { if (!seen[v]) q.push(v); } } `` Why is node 3 popped twice?

   The queue is a std::stack, so the nodes come out in the wrong order.seen[0] is never set, so node 0 is pushed again.The loop has no bound, so it always runs forever.The mark is set only when a node is popped, so node 3 is pushed by both node 1 and node 2 before its first pop.