Minimum Spanning Tree (MST)

Two algorithms

Complexity of Prim

The complexity of the above program is O(V²). If the input graph is represented using adjacency list, then the time complexity of Prim’s algorithm can be reduced to O(E log V) with the help of binary heap. — From GeeksforGeeks

Complexity of Kruskal

Time Complexity: O(ElogE) or O(ElogV). Sorting of edges takes O(ELogE) time. After sorting, we iterate through all edges and apply find-union algorithm. The find and union operations can take atmost O(LogV) time. So overall complexity is O(ELogE + ELogV) time. The value of E can be atmost O(V2), so O(LogV) are O(LogE) same. Therefore, overall time complexity is O(ElogE) or O(ElogV) .— From GeeksforGeeks

Problems

1168. Optimize Water Distribution in a Village

class Solution {
public:
vector<int> uf;
int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes)
{
uf.resize(n + 1, 0);
for (auto& p : pipes) swap(p[0], p[2]);
for (int i = 0; i < n; ++i)
{
uf[i + 1] = i + 1;
pipes.push_back({wells[i], 0, i + 1});
}
sort(pipes.begin(), pipes.end());
int res = 0;
for (int i = 0; n > 0; ++i)
{
int x = find(pipes[i][1]), y = find(pipes[i][2]);
if (x != y)
{
res += pipes[i][0];
uf[x] = y;
--n;
}
}
return res;
}
int find(int x)
{
if (x != uf[x]) uf[x] = find(uf[x]);
return uf[x];
}
};

Solution modified from [3]

class UF 
{
vector<int> root;
public:
UF(int N) : root(N)
{
for (int i = 0; i < N; ++i)
root[i] = i;
}

void union_(int x, int y)
{
root[find(y)] = root[find(x)];
}

int find(int x)
{
if (x != root[x])root[x] = find(root[x]);
return root[x];
}
};
class Solution {
public:
int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes)
{
// Represent the wells as additional pipes to a water-source node 0
for (int i = 1; i <= n; ++i)
pipes.push_back({0, i, wells[i-1]});

// Kruskal's algorithm
UF uf(n+1);
sort(pipes.begin(), pipes.end(), [](auto& a, auto& b){return a[2] < b[2];});
int ret = 0, i = 0;
for (auto& pipe : pipes)
{
if (uf.find(pipe[0]) != uf.find(pipe[1]))
{
++i;
ret += pipe[2];
if (i==n)break;
uf.union_(pipe[0], pipe[1]);
}
}
return ret;
}
};

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

Solution[1]

Reference

[1]https://zxi.mytechroad.com/blog/graph/leetcode-1489-find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/

[2] https://leetcode.com/problems/optimize-water-distribution-in-a-village/discuss/365853/C++PythonJava-Hidden-Well-in-House-0

[3]https://leetcode.com/problems/optimize-water-distribution-in-a-village/discuss/365835/C++-Kruskal's-algorithm-+-Clever-trick-(with-explanation)

Data Scientist/MLE/SWE @takemobi