MST edges and word ladder

Questions 1 to 5 of 8

1. 1. Predict the output. The program calls mstWeight four times on a triangle with edges 0-1 (weight 1), 1-2 (weight 2) and 0-2 (weight 3). The four results are printed in order, separated by spaces. ``cpp #include <algorithm> #include <iostream> #include <numeric> #include <vector> struct Edge { int a; int b; int weight; }; class DisjointSet { public: explicit DisjointSet(int n) : parent_(n), size_(n, 1) { for (int i = 0; i < n; ++i) parent_[i] = i; } int find(int x) { while (parent_[x] != x) { parent_[x] = parent_[parent_[x]]; x = parent_[x]; } return x; } bool unite(int a, int b) { int ra = find(a); int rb = find(b); if (ra == rb) return false; if (size_[ra] < size_[rb]) std::swap(ra, rb); parent_[rb] = ra; size_[ra] += size_[rb]; return true; } private: std::vector<int> parent_; std::vector<int> size_; }; long long mstWeight(int n, const std::vector<Edge>& edges, const std::vector<int>& order, int banned, int forced) { DisjointSet dsu(n); long long total = 0; int used = 0; if (forced >= 0) { const Edge& e = edges[forced]; dsu.unite(e.a, e.b); total += e.weight; ++used; } for (int i : order) { if (i == banned || i == forced) continue; const Edge& e = edges[i]; if (dsu.unite(e.a, e.b)) { total += e.weight; ++used; } } return used == n - 1 ? total : -1; } int main() { std::vector<Edge> edges = {{0, 1, 1}, {1, 2, 2}, {0, 2, 3}}; std::vector<int> order = {0, 1, 2}; std::cout << mstWeight(3, edges, order, -1, -1) << ' ' << mstWeight(3, edges, order, 0, -1) << ' ' << mstWeight(3, edges, order, -1, 2) << ' ' << mstWeight(3, edges, order, 2, -1) << '\n'; } ``

   3 3 4 33 5 3 33 5 4 33 5 4 1
2. 2. Predict the output. This is the word ladder solution from this lesson, with main making one call. ``cpp #include <cstddef> #include <iostream> #include <queue> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> std::string pattern(std::string word, std::size_t i) { word[i] = '*'; return word; } int ladderLength(const std::string& start, const std::string& target, const std::vector<std::string>& wordList) { const std::unordered_set<std::string> words(wordList.begin(), wordList.end()); if (!words.contains(target)) { return 0; } std::unordered_map<std::string, std::vector<std::string>> buckets; for (const auto& w : wordList) { for (std::size_t i = 0; i < w.size(); ++i) { buckets[pattern(w, i)].push_back(w); } } std::unordered_set<std::string> seen{start}; std::queue<std::pair<std::string, int>> q; q.push({start, 1}); while (!q.empty()) { auto [word, length] = q.front(); q.pop(); if (word == target) { return length; } for (std::size_t i = 0; i < word.size(); ++i) { auto it = buckets.find(pattern(word, i)); if (it == buckets.end()) { continue; } for (const auto& next : it->second) { if (seen.insert(next).second) { q.push({next, length + 1}); } } it->second.clear(); } } return 0; } int main() { std::cout << ladderLength("cold", "warm", {"cord", "card", "ward", "warm", "wold"}) << '\n'; return 0; } ``

   4506
3. 3. In the five-node network from this lesson's first worked example, edge 6 joins nodes 1 and 4 and has weight 6. Which group does it belong to?

   In neither groupCriticalPseudo-criticalCritical only if the weights are equal
4. 4. Why does ladderLength clear a bucket after reading it?

   Clearing the bucket frees memory, so the program can run on a larger word listThe first word that reads a bucket gives every word in it the smallest chain length possible, so a later read cannot add anything shorterWithout clearing, the buckets would hold the target word twice, and the search would return 0The clear call sorts the queue by word, so the search returns the alphabetically first chain
5. 5. Put the steps for one edge in the critical and pseudo-critical test, in the order the lesson's main loop runs them.

   Use the arrows to put the steps in order.

   1. 1.If the result is -1 or larger than best, mark the edge critical and move to the next edge↑↓
   2. 2.If the forced total equals best, mark the edge pseudo-critical↑↓
   3. 3.Otherwise run Kruskal with that edge forced in first↑↓
   4. 4.Run Kruskal with that edge banned, using the sorted order↑↓