Minimum Spanning Tree (MST)

Two algorithms

• Prim
• Kruskal

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)