Minimum Spanning Tree (Kruskal's Algorithm)

[Lekssays]

Problem: Minimum Spanning Tree: (Kruskal's Algorithm)

Input:

You are given a connected undirected graph G. You want to know what is the minimum spanning tree (a tree with the minimal total weighting of its edges )that connects all the vertices in the graph G.

Output:

Weight of the tree with the minimal total weighting of graph G's edges. (In this implementation, we displayed the edges that construct the MST)

Running Time:

E : Number of Edges, V : number of vertices

• Sorting : O(E log E)
• Union-find: O(log V)
• Overall: O(E log V)

  Implementation:

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define MAXN 30023
#define eps 1e-7

using namespace std;

struct edge {
    int u, v, w;

    bool operator < (edge o) const {
        if( abs(o.w - w) < eps )
            return pair<int, int>(u, v) < pair<int, int>(o.u, o.v);
        return w < o.w;
    }
};

int p[MAXN];
vector<edge> edgeList;
vector< pair<int,int> > connectedEdges;

int find(int u) {
    return p[u] == u ? u : find(p[u]);
}

void merge(int u, int v) {
    int pu = find(u), pv = find(v);
    p[pu] = pv;
}

int main(void){
    int u, v, w, n, e;

    while(true){
        cin >> n >> e;
        if(n == 0 && e == 0) return 0;
        edgeList.clear();
        connectedEdges.clear();
        for(int i = 0; i < e; i++){
            cin >> u >> v >> w;
            edgeList.push_back((edge){u, v, w});
        }

        sort(edgeList.begin(), edgeList.end());
        for(int i = 0; i < n; i++) p[i] = i;

        int res = 0;
        for(int i = 0; i < edgeList.size(); i++) {
            int u = edgeList[i].u, v = edgeList[i].v;
            if( find(u) == find(v) ) continue;
            merge(u, v);
            res += edgeList[i].w;
            if(edgeList[i].v > edgeList[i].u){
                connectedEdges.push_back(make_pair(edgeList[i].u, edgeList[i].v));
            } else {
                connectedEdges.push_back(make_pair(edgeList[i].v, edgeList[i].u));
            }
        }

        sort(connectedEdges.begin(), connectedEdges.end());
        if(res == 0 || connectedEdges.size() != n - 1) puts("Impossible");
        else {
            cout << res << endl;
            for (int i = 0; i < connectedEdges.size(); i++){
                cout << connectedEdges[i].first << " " << connectedEdges[i].second << endl;
            }
        }
    }
    return 0;
}

[saadtaame]

Everything is inside the main (except for the union-find code); this makes code hard to follow. This is a solution file for some problem ! I think that it's better to have code that is independent of solutions to particular problems: just the algorithm itself. It's up to the user to apply it to solve problems. I prefer not reading input at all and just giving the algorithm with sufficient details for the user..(same applies for other issues).

[Lekssays]

Ye.This is a solution of a specific problem in which they asked to keep track of the connected edges as well. That's why I shared the whole solution. What do you suggest to show the way to keep track of the edges?