Kruskal's Algorithm for MST 🚩🚩🚩

/*
->to find the MST using kruskal's algorithm
Steps:-
	1)sort the edges in acending order based on edge weight
	2)traverse on each edge
			->check if adding the current edge will make cycle or not(using the disjoint set union)
			->if yes ---> continue;
			->else
				->add that weight into the MST
			->break if the no of edges in MST in equal to n-1 (n == no of vertices)
            
 Time Complexity: O(ElogE) or O(ElogV). Sorting of edges takes O(ELogE) time. After sorting, we iterate through all edges and apply the find-union algorithm. The find and union operations can take at most O(LogV) time. So overall complexity is O(ELogE + ELogV) time. The value of E can be at most O(V2), so O(LogV) is O(LogE) the same. Therefore, the overall time complexity is O(ElogE) or O(ElogV)

*/


//this is Disjoint union stuff(respective functions are defined after the kruskal's function)
vector<ll> parent(100001), size(100001);
ll getSuperParent(ll v);
void makeUnion(ll a, ll b);


ll kruskal() {

	//taking the no of vertices and edges as input
	ll n, m;
	cin >> n >> m;

	//making the parent of all vertices as their own parent and size = 1(Disjoint Union stuff for cycle detection)
	for (int i = 0; i < n; i++) {
		parent[i] = i;
		size[i] = 1;
	}

	//storing the edges -> note that we are storing the edge weight first inorder to sort them later
	vector<pair<int, pair<int, int>>> e;

	//inputing the graph
	while (m--) {
		ll s, d, w;
		cin >> s >> d >> w;
		e.push_back({w, {s, d}});//pushing the edges into edges vector their weight first
	}

	sort(e.begin(), e.end());//sorting the vector of edges

	ll count = 0;//to count the edges in the MST
	ll ans = 0;// to store the weight of MST


	for (ll i = 0; i < e.size(); i++) {
		if (count == n - 1)//if no of edges is equal to no of vertices - 1 break(because MST contains only n-1 edges)
			break;
		ll src = e[i].second.first, dest = e[i].second.second, w = e[i].first;

		//checking if including the current edge will form a cycle or not if it does not then proceed futher
		if (getSuperParent(src) != getSuperParent(dest))
		{
			makeUnion(src, dest);
			cout << "[" << src << "-" << dest << "@" << w << "]" << endl;//printing the MST
			ans += w;//adding the weight of current edge into the ans
			count++;//increasing the no of edges into the MST
		}

	}

	cout << "Weight of MST is " << ans << endl;

	return ans;
}


//-----------------------------------------------------------------------------------
ll getSuperParent(ll v) {
	if (parent[v] == v)
		return v;
	return getSuperParent(parent[v]);
}

void makeUnion(ll a, ll b) {
	ll p_a = getSuperParent(a);
	ll p_b = getSuperParent(b);

	if (p_a == p_b)
		return;

	if (size[p_a] >= size[p_b]) {
		parent[p_b] = p_a;
		size[p_a] += size[p_b];
	} else {
		parent[p_a] = p_b;
		size[p_b] += size[p_a];
	}
}