implementation of kruskal's algorithm in C++

// C++ program for Kruskal's algorithm to find Minimum

// Spanning Tree of a given connected, undirected and

// weighted graph

#include<bits/stdc++.h>

using namespace std;

// Creating shortcut for an integer pair

typedef  pair<int, int> iPair;

// Structure to represent a graph

struct Graph

{

    int V, E;

    vector< pair<int, iPair> > edges;

    // Constructor

    Graph(int V, int E)

    {

        this->V = V;

        this->E = E;

    }

    // Utility function to add an edge

    void addEdge(int u, int v, int w)

    {

        edges.push_back({w, {u, v}});

    }

    // Function to find MST using Kruskal's

    // MST algorithm

    int kruskalMST();

};

// To represent Disjoint Sets

struct DisjointSets

{

    int *parent, *rnk;

    int n;

    // Constructor.

    DisjointSets(int n)

    {

        // Allocate memory

        this->n = n;

        parent = new int[n+1];

        rnk = new int[n+1];

        // Initially, all vertices are in

        // different sets and have rank 0.

        for (int i = 0; i <= n; i++)

        {

            rnk[i] = 0;

            //every element is parent of itself

            parent[i] = i;

        }

    }

    // Find the parent of a node 'u'

    // Path Compression

    int find(int u)

    {

        /* Make the parent of the nodes in the path

           from u--> parent[u] point to parent[u] */

        if (u != parent[u])

            parent[u] = find(parent[u]);

        return parent[u];

    }

    // Union by rank

    void merge(int x, int y)

    {

        x = find(x), y = find(y);

        /* Make tree with smaller height

           a subtree of the other tree  */

        if (rnk[x] > rnk[y])

            parent[y] = x;

        else // If rnk[x] <= rnk[y]

            parent[x] = y;

        if (rnk[x] == rnk[y])

            rnk[y]++;

    }

};

 /* Functions returns weight of the MST*/

int Graph::kruskalMST()

{

    int mst_wt = 0; // Initialize result

    // Sort edges in increasing order on basis of cost

    sort(edges.begin(), edges.end());

    // Create disjoint sets

    DisjointSets ds(V);

    // Iterate through all sorted edges

    vector< pair<int, iPair> >::iterator it;

    for (it=edges.begin(); it!=edges.end(); it++)

    {

        int u = it->second.first;

        int v = it->second.second;

        int set_u = ds.find(u);

        int set_v = ds.find(v);

        // Check if the selected edge is creating

        // a cycle or not (Cycle is created if u

        // and v belong to same set)

        if (set_u != set_v)

        {

            // Current edge will be in the MST

            // so print it

            cout << u << " - " << v << endl;

            // Update MST weight

            mst_wt += it->first;

            // Merge two sets

            ds.merge(set_u, set_v);

        }

    }

    return mst_wt;

}

// Driver program to test above functions

int main()

{

    /* Let us create above shown weighted

       and unidrected graph */

    int V = 9, E = 14;

    Graph g(V, E);

    //  making above shown graph

    g.addEdge(0, 1, 4);

    g.addEdge(0, 7, 8);

    g.addEdge(1, 2, 8);

    g.addEdge(1, 7, 11);

    g.addEdge(2, 3, 7);

    g.addEdge(2, 8, 2);

    g.addEdge(2, 5, 4);

    g.addEdge(3, 4, 9);

    g.addEdge(3, 5, 14);

    g.addEdge(4, 5, 10);

    g.addEdge(5, 6, 2);

    g.addEdge(6, 7, 1);

    g.addEdge(6, 8, 6);

    g.addEdge(7, 8, 7);

    cout << "Edges of MST are \n";

    int mst_wt = g.kruskalMST();

    cout << "\nWeight of MST is " << mst_wt;

    return 0;

}

Edges of MST are

          6 - 7

          2 - 8

          5 - 6

          0 - 1

          2 - 5

          2 - 3

          0 - 7

          3 - 4

         

          Weight of MST is 37

My Dear Shahrukh Khan Haters

My Dear Shahrukh Khan Haters

              First of all, Sharukh Khan is an Indian, a world famous person, he is not an egoist, always he respects women, he doesn’t have any religious feeling, more over he is a great Human Being.  If he had any religious bias feeling he will not marry 'Gouri Chibber' a Hindu women . If he is an egoist, we shouldn’t forget that we are also egoists in a way or other. If he doesn’t respect women, in his movies the titles will not show his heroin name before his. If he had any bad qualities he shall never become world’s most admirable person. How can you tell him to go to Pakistan, as if whole India is your property! How are you telling that I am an Indian, he is also an Indian like us? How we are living in this place he also has full rights to live here, who are you to oppose him, next time come with proper evidence and talk. What is wrong with his daughter’s dress, who are you to abject? In the first place her father and mother don’t have any problem with that, who are you to talk about it? Who are we to tell a woman what to wear or what not to?  Who made these borders, who made these religions, what is the use of these religious boundaries? May be long days ago for some reasons these all made by our ancestors.  But we without thinking twice fight each day to tell that “I am Great”. We never know what happens to us in the next minute. We never know what happens afterlife. People change their behavior day by day by their past experiences. If we point out, irritate iconic persons with our stupid thoughts they also Change, they will eventually will stop to help other who are in need. I feel proud that Shahrukh Khan is born in India, that’s my country too. In our house we don’t even like our brothers’ & sisters’ behavior, how can we like other people who live next to our house, state, country, religion. We need to change ourselves, automatically whole world will change- Why because human brain is a mirror, what we see is what we learn. May be one day our children can become good or bad persons that will depend upon our behavior.  Next time before we think or point fingers at others let’s just think what we need to do to succeed in our life, how to become world famous or at the least how to be a good human being. And Don’t You Dare to criticize my Shahruk.  I don’t need any likes and dislikes for this Article. I am deeply hurt by the way society is ruining a persons’ reputations based on their Religion. That is the sole reason I wrote this article. Do not use any degrading words in the comments to show off, it just makes you less Human Being!

                                                                                               from

                                                                                             Swapna