| 43 | }; |
| 44 | |
| 45 | int connectTheDots(std::vector<std::vector<int>>& points) { |
| 46 | int n = points.size(); |
| 47 | // Create and populate a list of all possible edges. |
| 48 | std::vector<std::tuple<int, int, int>> edges; |
| 49 | for (int i = 0; i < n; i++) { |
| 50 | for (int j = i + 1; j < n; j++) { |
| 51 | // Manhattan distance. |
| 52 | int cost = std::abs(points[i][0] - points[j][0]) + std::abs(points[i][1] - points[j][1]); |
| 53 | edges.push_back(std::make_tuple(cost, i, j)); |
| 54 | } |
| 55 | } |
| 56 | // Sort the edges by their cost in ascending order. |
| 57 | std::sort(edges.begin(), edges.end()); |
| 58 | UnionFind uf(n); |
| 59 | int totalCost = 0; |
| 60 | int edgesAdded = 0; |
| 61 | // Use Kruskal's algorithm to create the MST and identify its minimum cost. |
| 62 | for (auto& edge : edges) { |
| 63 | int cost, p1, p2; |
| 64 | std::tie(cost, p1, p2) = edge; |
| 65 | // If the points are not already connected (i.e. their representatives are |
| 66 | // not the same), connect them, and add the cost to the total cost. |
| 67 | if (uf.unionSets(p1, p2)) { |
| 68 | totalCost += cost; |
| 69 | edgesAdded++; |
| 70 | // If n - 1 edges have been added, the MST is complete. |
| 71 | if (edgesAdded == n - 1) { |
| 72 | return totalCost; |
| 73 | } |
| 74 | } |
| 75 | } |
| 76 | return totalCost; |
| 77 | } |