Minimum Spanning Trees (MST)
1584. Min Cost to Connect All Points
class UnionFind {
vector<int> root;
public:
UnionFind(int n) {
root.resize(n);
iota(root.begin(), root.end(), 0);
}
int find(int p) {
while (p != root[p]) {
root[p] = root[root[p]]; // Path compression
p = root[p];
}
return p;
}
void connect(int a, int b) {
int rootA = find(a), rootB = find(b);
if (rootA != rootB) {
root[rootA] = rootB;
}
}
};
class Solution {
private:
vector<array<int, 3>> edges;
int getDist(int i, int j, const vector<vector<int>>& points) {
return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
}
public:
int minCostConnectPoints(vector<vector<int>>& points) {
int n = points.size();
if (n == 1) return 0;
// Generate all unique edges (i, j, cost)
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
edges.push_back({i, j, getDist(i, j, points)});
}
}
// Sort edges by cost
sort(edges.begin(), edges.end(), [](const auto& a, const auto& b) {
return a[2] < b[2];
});
UnionFind uf(n);
int cost = 0, connected = 0;
// Kruskal's algorithm
for (const auto& e : edges) {
int a = e[0], b = e[1], w = e[2];
if (uf.find(a) != uf.find(b)) {
uf.connect(a, b);
cost += w;
connected++;
if (connected == n - 1) return cost;
}
}
return -1; // Should not happen for valid input
}
};
public int minCostConnectPoints(int[][] points) {
int n = points.length;
boolean[] visited = new boolean[n];
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[0] = 0;
int result = 0;
for (int i = 0; i < n; i++) {
int curt = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && (curt == -1 || minDist[j] < minDist[curt])) {
curt = j;
}
}
visited[curt] = true;
result += minDist[curt];
for (int j = 0; j < n; j++) {
if (visited[j]) continue;
int cost = Math.abs(points[curt][0] - points[j][0]) + Math.abs(points[curt][1] - points[j][1]);
if (minDist[j] > cost) {
minDist[j] = cost;
}
}
}
return result;
}1135. Connecting Cities With Minimum Cost
class UnionFind {
private:
vector<int> root;
vector<int> weights;
public:
UnionFind(int n) {
root.resize(n);
weights.resize(n, 1);
iota(root.begin(), root.end(), 0);
}
int find(int p) {
while (p != root[p]) {
root[p] = root[root[p]];
p = root[p];
}
return p;
}
void connect(int x, int y) {
int rootX = find(x), rootY = find(y);
if (weights[rootX] > weights[rootY]) {
root[rootY] = rootX;
} else {
root[rootX] = rootY;
}
}
};
class Solution {
public:
int minimumCost(int n, vector<vector<int>>& connections) {
sort(connections.begin(), connections.end(), [](const vector<int>& a, const vector<int>& b){
return a[2] < b[2];
});
UnionFind uf(n + 1);
int cost = 0, edges = 0;
for (const auto& conn: connections) {
int a = conn[0], b = conn[1];
int rootA = uf.find(a), rootB = uf.find(b);
if (rootA != rootB) {
uf.connect(a, b);
cost += conn[2];
edges += 1;
}
}
return edges == n - 1 ? cost : -1;
}
};public int minimumCost(int n, int[][] connections) {
// Build adjacency map: city -> list of (neighbor, cost)
Map<Integer, List<int[]>> graph = new HashMap<>();
for (int i = 1; i <= n; i++) {
graph.put(i, new ArrayList<>());
}
for (int[] conn : connections) {
graph.get(conn[0]).add(new int[]{conn[1], conn[2]});
graph.get(conn[1]).add(new int[]{conn[0], conn[2]});
}
boolean[] visited = new boolean[n + 1];
int[] minCost = new int[n + 1];
Arrays.fill(minCost, Integer.MAX_VALUE);
minCost[1] = 0; // Start from city 1
int result = 0, count = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{1, 0}); // [city, cost]
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int city = curr[0];
int cost = curr[1];
if (visited[city]) continue;
visited[city] = true;
result += cost;
count++;
for (int[] next : graph.get(city)) {
int nextCity = next[0];
int nextCost = next[1];
if (!visited[nextCity] && nextCost < minCost[nextCity]) {
minCost[nextCity] = nextCost;
pq.offer(new int[]{nextCity, nextCost});
}
}
}
return (count == n) ? result : -1;
}1168. Optimize Water Distribution in a Village
class UnionFind {
vector<int> parent;
public:
UnionFind(int n) {
parent.resize(n);
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
if (x != parent[x]) {
parent[x] = find(parent[x]);
}
return parent[x];
}
bool connect(int a, int b) {
int rootA = find(a), rootB = find(b);
if (rootA == rootB) return false;
parent[rootA] = rootB;
return true;
}
};
class Solution {
private:
vector<array<int, 3>> edges;
public:
int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
for (int i = 0; i < wells.size(); ++i) {
edges.push_back({i + 1, 0, wells[i]});
}
for (vector<int> p : pipes) {
edges.push_back({p[0], p[1], p[2]});
}
sort(edges.begin(), edges.end(), [](const auto& a, const auto& b){
return a[2] < b[2];
});
UnionFind uf(n + 1);
int total_cost = 0, count = 0;
for (const auto& [a, b, cost] : edges) {
if (uf.connect(a, b)) {
total_cost += cost;
}
}
return total_cost;
}
};public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
// Build graph
Map<Integer, List<int[]>> graph = new HashMap<>();
for (int i = 0; i <= n; i++) {
graph.put(i, new ArrayList<>());
}
// Add edges from virtual node 0 to each house with well cost
for (int i = 1; i <= n; i++) {
graph.get(0).add(new int[]{i, wells[i-1]});
graph.get(i).add(new int[]{0, wells[i-1]});
}
for (int[] pipe : pipes) {
int house1 = pipe[0];
int house2 = pipe[1];
int cost = pipe[2];
graph.get(house1).add(new int[]{house2, cost});
graph.get(house2).add(new int[]{house1, cost});
}
int[] minCost = new int[n + 1];
Arrays.fill(minCost, Integer.MAX_VALUE);
minCost[0] = 0;
boolean[] visited = new boolean[n + 1];
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1] - b[1]);
pq.offer(new int[]{0, 0});
int result = 0;
while (!pq.isEmpty()) {
int[] curt = pq.poll();
int house = curt[0], cost = curt[1];
if (visited[house]) continue;
visited[house] = true;
result += cost;
for (int[] next : graph.get(house)) {
int nextHouse = next[0], nextCost = next[1];
if (!visited[nextHouse] && nextCost < minCost[nextHouse]) {
minCost[nextHouse] = nextCost;
pq.offer(new int[]{nextHouse, nextCost});
}
}
}
return result;
}Last updated
Was this helpful?