4.Kruskal (MST)

Algorithm

// Initialize result
mst_weight = 0

// Create V single item sets
for each vertex v
	parent[v] = v;
	rank[v] = 0;

Sort all edges into non decreasing 
order by weight w

for each (u, v) taken from the sorted list  E
    do if FIND-SET(u) != FIND-SET(v)
        print edge(u, v)
        mst_weight += weight of edge(u, v)
        UNION(u, v)

Code:

#include <bits/stdc++.h>

using namespace std;

int findPar(vector<int> &parent, int node)
{

    if (parent[node] == -1)
    {
        return node;
    }

    parent[node] = findPar(parent, parent[node]);
    return parent[node];
}

void uni(vector<int> &parent, vector<int> &rank, int a, int b)
{
    int parA = findPar(parent, a);
    int parB = findPar(parent, b);

    if (parA != parB)
    {

        if (rank[parA] > rank[parB])
        {
            parent[parB] = parA;
        }
        else if (rank[parB] > rank[parA])
        {
            parent[parA] = parB;
        }
        else
        {
            parent[parA] = parB;
            rank[parB]++;
        }
    }
    return;
}

int main()
{
    int n, m;
    cin >> n >> m;

    vector< pair<int, pair<int, int>> > v;
    vector<int> parent(n + 1, -1);
    vector<int> rank(n + 1, 0);
    for (int k = 1; k <= m; k++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        v.push_back({w, {a, b}});
    }

    sort(v.begin(), v.end());
    int minWeight = 0;
    for (auto itr = v.begin(); itr != v.end(); itr++)
    {
        pair<int, int> p = itr->second;
        int x = p.first;
        int y = p.second;

        int pa = findPar(parent,x);
        int py = findPar(parent,y);

        if (pa != py)
        {
            uni(parent, rank, x, y);
            minWeight = minWeight + itr->first;
        }

    }

    cout << minWeight;

    return 0;
}

Time Complexity: O(E logE) or O(E logV). Sorting of edges takes O(E Log E) 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(E Log E + E Log V) time.