# 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;    }};`

Solution[1]

# Reference

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi