Hello, I'm having trouble finding the correct Second best MST The procedures i follow are :
Finding MST by kruskal
Iterate over all edges of the found MST and refrain from taking each edge individually
Rerunning Kruskal to find MST
trace the minimum found MST
Here is my code
#define push_back pb
#define make_pair mp
vector < pair < int, int >> taken; //Used to store edges taken in MST
for (int i = 0; i < e; i++) { //Finding initial MST
pair < int, ii > front = EdgeList[i];
if (!isSameSet(front.second.first, front.second.second)) {
mst_cost += front.first;
taken.pb(mp(front.second.first, front.second.second)); //Adding taken edge
unionSet(front.second.first, front.second.second);
}
}
int secondMST = INF;
for (int i = 0; i < taken.size(); i++) {
initSet(n + 1);
int tempst = 0;
for (int j = 0; j < e; j++) {
pair < int, ii > front = EdgeList[j];
if ((front.second.first == taken[i].first) && (front.second.second == taken[i].second))
continue;
else if (!isSameSet(front.second.first, front.second.second)) {
tempst += front.first;
unionSet(front.second.first, front.second.second);
}
}
secondMST = min(secondMST, tempst);
}
cout << mst_cost << " " << secondMST << endl;