MST Archives - Huahua's Tech Road

花花酱 LeetCode 1584. Min Cost to Connect All Points

By zxi on September 13, 2020

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [x_i, y_i].

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

Example 1:

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation:

We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.

Example 2:

Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18

Example 3:

Input: points = [[0,0],[1,1],[1,0],[-1,1]]
Output: 4

Example 4:

Input: points = [[-1000000,-1000000],[1000000,1000000]]
Output: 4000000

Example 5:

Input: points = [[0,0]]
Output: 0

Constraints:

1 <= points.length <= 1000
-10⁶ <= x_i, y_i <= 10⁶
All pairs (x_i, y_i) are distinct.

Solution: Minimum Spanning Tree

Kruskal’s algorithm
Time complexity: O(n^2logn)
Space complexity: O(n^2)
using vector of vector, array, pair of pair, or tuple might lead to TLE…

C++

struct Edge {

int cost;

int x;

int y;

bool operator<(const Edge& e) const { return cost < e.cost; }

};

class Solution {

public:

int minCostConnectPoints(vector<vector<int>>& points) {

const int n = points.size();

vector<Edge> edges(n * (n - 1) / 2); // {cost, i, j}

for (int i = 0, idx = 0; i < n; ++i)

for (int j = i + 1; j < n; ++j)

edges[idx++] = {abs(points[i][0] - points[j][0]) +

abs(points[i][1] - points[j][1]), i, j};

std::sort(begin(edges), end(edges));

vector<int> p(n);

std::iota(begin(p), end(p), 0);

vector<int> rank(n, 0);

int ans = 0;

int count = 0;

for (const auto& e : edges) {

int rx = find(p, e.x);

int ry = find(p, e.y);

if (rx == ry) continue;

ans += e.cost;

if (rank[rx] < rank[ry]) swap(rx, ry);

p[rx] = ry;

rank[ry] += rank[rx] == rank[ry];

if (++count == n - 1) break;

}

return ans;

}

private:

int find(vector<int>& p, int x) const {

while (p[x] != x) {

int tp = p[x];

p[x] = p[p[x]];

x = tp;

}

return x;

}

};

Prim’s Algorithm
ds[i] := min distance from i to ANY nodes in the tree.

Time complexity: O(n^2) Space complexity: O(n)

C++

class Solution {

public:

int minCostConnectPoints(vector<vector<int>>& points) {

const int n = points.size();

auto dist = [](const vector<int>& pi, const vector<int>& pj) {

return abs(pi[0] - pj[0]) + abs(pi[1] - pj[1]);

};

vector<int> ds(n, INT_MAX);

for (int i = 1; i < n; ++i)

ds[i] = dist(points[0], points[i]);

int ans = 0;

for (int i = 1; i < n; ++i) {

auto it = min_element(begin(ds), end(ds));

const int v = distance(begin(ds), it);

ans += ds[v];

ds[v] = INT_MAX; // done

for (int i = 0; i < n; ++i) {

if (ds[i] == INT_MAX) continue;

ds[i] = min(ds[i], dist(points[i], points[v]));

}

return ans;

}

};

花花酱 LeetCode 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

By zxi on June 26, 2020

Given a weighted undirected connected graph with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [from_i, to_i, weight_i] represents a bidirectional and weighted edge between nodes from_i and to_i. A minimum spanning tree (MST) is a subset of the edges of the graph that connects all vertices without cycles and with the minimum possible total edge weight.

Find all the critical and pseudo-critical edges in the minimum spanning tree (MST) of the given graph. An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. A pseudo-critical edge, on the other hand, is that which can appear in some MSTs but not all.

Note that you can return the indices of the edges in any order.

Example 1:

Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
Output: [[0,1],[2,3,4,5]]
Explanation: The figure above describes the graph.
The following figure shows all the possible MSTs:

Notice that the two edges 0 and 1 appear in all MSTs, therefore they are critical edges, so we return them in the first list of the output.
The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges. We add them to the second list of the output.

Example 2:

Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
Output: [[],[0,1,2,3]]
Explanation: We can observe that since all 4 edges have equal weight, choosing any 3 edges from the given 4 will yield an MST. Therefore all 4 edges are pseudo-critical.

Constraints:

2 <= n <= 100
1 <= edges.length <= min(200, n * (n - 1) / 2)
edges[i].length == 3
0 <= from_i < to_i < n
1 <= weight_i <= 1000
All pairs (from_i, to_i) are distinct.

Solution: Brute Force?

For each edge
1. exclude it and build a MST, cost increased => critical
2. for a non critical edge, force include it and build a MST, cost remains the same => pseudo critical

Proof of 2, if a non critical / non pseudo critical edge was added into the MST, the total cost must be increased. So if the cost remains the same, must be the other case. Since we know the edge is non-critical, so it has to be pseudo critical.

C++

// Author: Huahua

class UnionFind {

public:

explicit UnionFind(int n): p_(n), r_(n) { iota(begin(p_), end(p_), 0); } // e.g. p[i] = i

int Find(int x) { return p_[x] == x ? x : p_[x] = Find(p_[x]); }

bool Union(int x, int y) {

int rx = Find(x);

int ry = Find(y);

if (rx == ry) return false;

if (r_[rx] == r_[ry]) {

p_[rx] = ry;

++r_[ry];

} else if (r_[rx] > r_[ry]) {

p_[ry] = rx;

} else {

p_[rx] = ry;

}

return true;

}

private:

vector<int> p_, r_;

};

class Solution {

public:

vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {

// Record the original id.

for (int i = 0; i < edges.size(); ++i) edges[i].push_back(i);

// Sort edges by weight.

sort(begin(edges), end(edges), [&](const auto& e1, const auto& e2){

if (e1[2] != e2[2]) return e1[2] < e2[2];

return e1 < e2;

});

// Cost of MST, ex: edge to exclude, in: edge to include.

auto MST = [&](int ex = -1, int in = -1) -> int {

UnionFind uf(n);

int cost = 0;

int count = 0;

if (in >= 0) {

cost += edges[in][2];

uf.Union(edges[in][0], edges[in][1]);

count++;

}

for (int i = 0; i < edges.size(); ++i) {

if (i == ex) continue;

if (!uf.Union(edges[i][0], edges[i][1])) continue;

cost += edges[i][2];

++count;

}

return count == n - 1 ? cost : INT_MAX;

};

const int min_cost = MST();

vector<int> criticals;

vector<int> pseudos;

for (int i = 0; i < edges.size(); ++i) {

// Cost increased or can't form a tree.

if (MST(i) > min_cost) {

criticals.push_back(edges[i][3]);

} else if (MST(-1, i) == min_cost) {

pseudos.push_back(edges[i][3]);

}

return {criticals, pseudos};

}

};

花花酱 Minimum Spanning Tree (MST) 最小生成树 SP18

By zxi on January 24, 2020

Prim’s Algorithm

Time complexity: O(ElogV)
Space complexity: O(V+E)

C++

// Author: Huahua

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

int main(int argc, char** argv) {

const int n = 4;

vector<vector<int>> edges{{0,1,1},{0,3,3},{0,2,6},{2,3,2},{1,2,4},{1,3,5}};

vector<vector<pair<int, int>>> g(n);

for (const auto& e : edges) {

g[e[0]].emplace_back(e[1], e[2]);

g[e[1]].emplace_back(e[0], e[2]);

}

priority_queue<pair<int, int>> q; // (-w, v)

vector<int> seen(n);

q.emplace(0, 0); // (-w, v)

int cost = 0;

for (int i = 0; i < n; ++i) {

while (true) {

const int w = -q.top().first;

const int v = q.top().second;

q.pop();

if (seen[v]++) continue;

cost += w;

for (const auto& p : g[v]) {

if (seen[p.first]) continue;

q.emplace(-p.second, p.first);

}

break;

}

cout << cost << endl;

return 0;

}

Python

# Author: Huahua

from collections import defaultdict

from heapq import *

n = 4

edges = [[0,1,1],[0,3,3],[0,2,6],[2,3,2],[1,2,4],[1,3,5]]

g = defaultdict(list)

for e in edges:

g[e[0]].append((e[1], e[2]))

g[e[1]].append((e[0], e[2]))

q = []

cost = 0

seen = set()

heappush(q, (0, 0))

for _ in range(n):

while True:

w, u = heappop(q)

if u in seen: continue

cost += w

seen.add(u)

for v, w in g[u]:

if v in seen: continue

heappush(q, (w, v))

break

print(cost)

Kruskal’s Algorithm

Time complexity: O(ElogV)
Space complexity: O(V+E)

C++

// Author: Huahua

#include <iostream>

#include <queue>

#include <vector>

#include <functional>

#include <numeric>

using namespace std;

int main(int argc, char** argv) {

const int n = 4;

vector<vector<int>> edges{{0,1,1},{0,3,3},{0,2,6},{2,3,2},{1,2,4},{1,3,5}};

vector<vector<int>> q; // (w, u, v)

for (const auto& e : edges)

q.push_back({e[2], e[0], e[1]});

sort(begin(q), end(q));

vector<int> p(n);

iota(begin(p), end(p), 0);

function<int(int)> find = [&](int x) {

return x == p[x] ? x : p[x] = find(p[p[x]]);

};

int cost = 0;

for (const auto& t : q) {

int w = t[0], u = t[1], v = t[2];

int ru = find(u), rv = find(v);

if (ru == rv) continue;

p[ru] = rv; // merge (u, v)

cost += w;

}

cout << cost << endl;

return 0;

}

Python

from collections import defaultdict

from heapq import *

n = 4

edges = [[0,1,1],[0,3,3],[0,2,6],[2,3,2],[1,2,4],[1,3,5]]

p = list(range(n))

def find(x):

if x != p[x]: p[x] = find(p[p[x]])

return p[x]

cost = 0

for u, v, w in sorted(edges, key=lambda x: x[2]):

ru, rv = find(u), find(v)

if ru == rv: continue

p[ru] = rv

cost += w

print(cost)

Posts tagged as “MST”

花花酱 LeetCode 1584. Min Cost to Connect All Points

Solution: Minimum Spanning Tree

C++

C++

花花酱 LeetCode 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Solution: Brute Force?

C++

花花酱 Minimum Spanning Tree (MST) 最小生成树 SP18

Prim’s Algorithm

C++

Python

Kruskal’s Algorithm

C++

Python