Kruskal Algorithm

Minimum Cost Spanning Tree By Kruskal Algorithm using priority_queue in c++

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
int main()
{
    int n,e;
    while(cin>>n>>e&&n&&e)
    {
        int belongs[n];
        for(int i=0;i<n;i++)
            belongs[i]=i;
        priority_queue< pair<int, ii> > EdgeList;
        int u,v,w;
        long long cost=0;
        for(int i=0;i<e;i++)
        {
            cin>>u>>v>>w;
            EdgeList.push(make_pair(-w,make_pair(u,v)));
            cost+=w;
        }
        long long mst_cost=0;
        vector<pair<int,int> > MST;
         while (!EdgeList.empty())
         {

            pair<int, ii> front = EdgeList.top();
            EdgeList.pop();
          int X=front.second.first;
          int Y=front.second.second;
          //x=Find(belongs,x);
          int x=belongs[X];
          //y=Find(belongs,y);
          int y=belongs[Y];
          if(x!=y){
           mst_cost += (-front.first);
           cout<<X<<"-"<<Y<<endl;
           MST.push_back(make_pair(X,Y));
           //union1(belongs,x,y,n);
           for(int i=0;i<n;i++){
            if(belongs[i]==y)
            belongs[i]=x;
            }
          }
         }
         cout<<cost-mst_cost<<endl;
         cout<<"Minimum Cost Spanning Tree\n";
         for(int i=0;i<MST.size();i++)
         {
             cout<<"Source "<<MST[i].first<<" Destination "<<MST[i].second<<endl;
         }
    }
    return 0;
}

BFS Traversal using <Vector> in C++

/** Node Starts from 0 not 1.
    This program will traverse all the nodes from a starting point*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int node;
    while(cin>>node)
    {
        int edge;
        cin>>edge;
        vector<int> Graph[node];
        int Visit[node];
        memset(Visit,-1,sizeof(Visit));
        int u,v;
        while(edge--)
        {
            cin>>u>>v;
            Graph[u].push_back(v);
            Graph[v].push_back(u);
        }
        queue<int> bi;
        int startNode;
        cin>>startNode;
        bi.push(startNode);Visit[startNode]=1;
        while(!bi.empty())
        {
            int f=bi.front();
            cout<<f<<"-->";
            bi.pop();
            for(vector<int>::iterator it=Graph[f].begin();it!=Graph[f].end();it++)
            {
                if(Visit[*it]==-1)
                {
                    Visit[*it]=1;
                    bi.push(*it);
                }
            }
        }
        cout<<"end\n";
    }
    return 0;
}

DFS Traversal using <Vector> in C++

/*************
!done
**************/
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int nodes,edges;
    while(cin>>nodes>>edges){
        vector<int> Graph[nodes];
        int u,v;
        while(edges--)
        {
            cin>>u>>v;
            Graph[u].push_back(v);
            //Graph[v].push_back(u);
        }
        int Visit[nodes];
        memset(Visit,-1,sizeof(Visit));
        stack<int> st;
        int start;
        cin>>start;
        st.push(start);
        Visit[start]=1;
        while(!st.empty())
        {
            int top=st.top();
            st.pop();
            cout<<top<<"-->";
            for(vector<int>::iterator i=Graph[top].begin();i!=Graph[top].end();i++)
            {
                if(Visit[*i]==-1) {
                    st.push(*i);
                    Visit[*i]=1;
                }
            }
        }
        cout<<"-->end\n";
    }
    return 0;
}

Using Divide And Conqure Technique finding maximum and minimum value of an array

Language C++

/************
done!
************/
#include<bits/stdc++.h>

using namespace std;

int a[1000];

void DAndCMaxMin(int i,int j,int &maxx,int &minx)
{
    int min1,max1;

    if(i==j){/**smallp*/

    maxx=a[i];

    minx=a[i];

    return;

    }

    if( i==j-1 )/**smallp*/

    {

        if(a[i]<a[j]){

            maxx=a[j];

            minx=a[i];

        }

        else

        {

            maxx=a[i];

            minx=a[j];

        }

        return;

    }

    else

    {

        int mid=(i+j)/2;

        /************

        dividing part

        ************/

        DAndCMaxMin(i,mid,maxx,minx);

        DAndCMaxMin(mid+1,j,max1,min1);

        /*************

        combining part

        *************/

        if(maxx<max1)

            maxx=max1;

        if(minx>min1)

            minx=min1;

    }
}

int main()

{

    int n;

    while(cin>>n)

    {

        int maxx=0,minx=0;

        for(int i=0;i<n;i++)
            cin>>a[i];

        DAndCMaxMin(0,n-1,maxx,minx);

        cout<<"Maximum value is "<<maxx<<endl;

        cout<<"Minimum value is "<<minx<<endl;

    }
    return 0;
}

Java:Sorting an array

//This program will take some random values and sort them in ascending order

import static java.lang.Math.abs;
import java.util.*;

public class SortingAnArray {

    public static void main(String[] args) {

        Scanner obj=new Scanner(System.in);
        int n;
        n=obj.nextInt();
        int a[]=new int[n];
        Random ob=new Random();
        for(int i=0;i<n;i++)
        {
            a[i]=ob.nextInt()%9;
            if(a[i]<0)
                a[i]=abs(a[i]);
        }
        System.out.println("Elements before sorting");
        for(int i:a)
        {
            System.out.printf("%d ",i);
        }
        System.out.println();
        Arrays.sort(a);
        System.out.println("Elements after sorting");
        for(int i:a)
        {
            System.out.printf("%d ",i);
        }
        System.out.println();
    }
   
}

STL:<stack> container

For using stack container we have to include <stack> in our program.We already know that stack is last in first out system.Mainly stack has two operations 1.push operation & 2.pop operation.

There are 5 member functions in the <stack> container.They are:

Suppose x is a stack

1.x.push(value);//for inserting a value in stack.

2.x.pop();//for removing the top element.

3.x.top();returns the top element of the stack.

4.x.empty();returns a boolean value that the is empty or not.

5.x.clear();for removing the entire stack.

SORTING A LINKED LIST

/*******************
linked list
bubble sort
complexity:O(n^2)
*******************/
#include <bits/stdc++.h>

using namespace std;

class linked_list
{
    public:
    int data;
    class linked_list *next;
};
typedef linked_list node;

void show(node *p){

    while(p){
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
    return;
}
void sort(node *p)
{
    while(p->next){
        node *test=p->next;
        while(test){
            if(test->data<p->data)
                swap(test->data,p->data);
            test=test->next;
        }
        p=p->next;
    }
}
void create(node *p){

    char c;
    scanf("%d%c", &p->data, &c);

    if(c=='\n')
        p->next=NULL;
    else
    {
        p->next=new node;
        create(p->next);
    }
    return;
}

int main(){

    bool x;
    while(cin>>x){

        node *head;
        head=new node;
        create(head);
        cout<<"list before sorting\n";
        show(head);
        sort(head);
        cout<<"list after sorting\n";
        show(head);
    }
    return 0;
}