MST proper implementation

general
, ,
1

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])
            continue;
        vis[wts[i].second.first] = 1;
        vis[wts[i].second.second] = 1;
        ans += wts[i].first;
        c++;
        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?

2

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
4

Why not. Pls prove.

5

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.

6

Got it. Thanks Man!