MST proper implementation

I read about finding the Minimum Spanning Tree using kruskal’s Algorithm.I am trying the same algorithm to find Max. Spanning Tree.So, I made a vector of type<int,<int,int>> where first int here represents the weight of edge and 2nd and 3rd int are the vertices between which the edge is. After taking the input I sorted it in Descending order and then finally i greedily approached it by taking the maximum weight edged into the tree. To check that cycles are not being formed, I made a map vis which would map every visited node to one.
#include <bits/stdc++.h>
using namespace std;
map<int, int> vis;
int n, m;
vector<pair<int, pair<int, int>>> wts;

int mst()
    int ans = 0,c=0;
    for (int i = 0; i < m; i++)
        if (vis[wts[i].second.first] && vis[wts[i].second.second])
        vis[wts[i].second.first] = 1;
        vis[wts[i].second.second] = 1;
        ans += wts[i].first;
        if(c>=n-1) break;//tree formation done
    return ans;

int main()
cin >> n >> m;
for (int i = 0; i < m; i++)
    int a, b, c;
    cin >> a >> b >> c;
    wts.push_back({c, {a, b}});
sort(wts.begin(), wts.end(), greater<pair<int, pair<int, int>>>());

cout << mst()<<endl;

I took the condition of a cycle being formed as when the vertices of the edge i am taking into consideration are already both visited.

Apparently it is not working. It is given W.A.
Where could it be going wrong?

we can’t find cycle just by vis array
for ex. N = 6
and you added 2 edges
1-2 and 2-3
so vis[1] = vis[2] = vis[3] = true

now if u add edge 4 -5, so vis[4] = vis[5] = true

and if next smallet edge is 3-4 then you just skipped it , but that’s not the case.

solution : use DSU (O(nlogn)) or without DSU but O(n^2) code

1 Like

Why not. Pls prove.

use dsu instead.
bcoz, suppose, if there are 2 components (max. span. tree).
there must be an edge which connects this two components.
but acc. to ur code it will not be connected.(atlast u will get max. span. forrest instead of max. span. tree.
which gives u WA)

tip : use DSU instead of vis array.

Got it. Thanks Man!