SOME OF THE BASIC TERM'S  REALTED  TO GRAPH THEORY

1. VERTEX COVER :-
        vertex cover of a graph is a set of vertices such that each edge of the graph is incident to atleast  one vertex of the set.

     In the above figure the vertex in the red color are vertex cover.

2. Minimum Vertex cover :-
        Minimum vertex cover problem for genaral graph (except Bipartite Graph)  is a optimization   problem in computer science. Minimum vertex cover is a vertex cover of smallest possible size.
   

       I think you understand by the example of figure's. see the difference in the figure of vertex cover and minimum vertex cover.

3. MATCHING :-
        A Matching or (Independent set of edges) is a set of edges without common vertices.
                   
                          

        In the figure set of red edges are matching.

4.MAXIMAL MATCHING :-
        A Maximal matching is also a matching of the graph ,such that it is not a proper subset of   any other matching in the graph.
        A maximal matching has a property if add another new edge that is not in matching ,it is no   longer a matching.
                                      

5.MAXIMUM MATCHING :-
        A Maximum matching is a maximal matching that containg largest possible number of edges.  Every maximum matching is maximal but not every maximal matching is maximum.

6. PERFECT MATCHING :-
        A Perfect matching is the matching which matches all the vertices of the graph.

7. NEAR PERFECT MATCHING :-
        A Near perfect matching is one in which exactly one vertex is unmatched. This can only occur when the graph has odd number of  vertices,such a matching must be maximum.
8.EDGE COVER :-
        Edge cover is a set of edges ,such that every vertex of grpah is incident to atleast one edge of the  set.

Some Normal Codes of Binary Tree and Binary Search Trees :)

A  Binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• The left and right subtree must each also be a binary search tree.

• There must be no duplicate nodes. 

I assume you know very well the insertion ,searching ,and some basics so I am not explain here . For more information refer Wikipedia .

Deletion

There are three possible cases to consider:

• Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.
• Deleting a node with one child: Remove the node and replace it with its child.
• Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-order predecessor node, R. Replace the value of N with the value of R, then delete R.

As with all binary trees, a node's in-order successor is the left-most child of its right subtree, and a node's in-order predecessor is the right-most child of its left subtree. In either case, this node will have zero or one children. Delete it according to one of the two simpler cases above.

 #include<string.h>
#include<cstdlib>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<iostream>
using namespace std;
struct node{
    int data;
    struct node* left;
    struct node* right;
};
struct Link_list_address_return
{
    struct node* first;
    struct node* last;
};
struct node* NEW(int i)
{
struct node* NODE=(struct node*)malloc(sizeof(struct node));
NODE->data=i;
NODE->left=NULL;
NODE->right=NULL;
return (NODE);
}
struct node* CASE1(struct node* root,struct node* par,struct node* Node)  /*FOR LEAF NODE */
{
    if(par==NULL)
        root=NULL;
    else if(Node==par->left)
        par->left=NULL;
    else
        par->right=NULL;
    free(Node);
return root;
}
struct node* CASE2(struct node* root,struct node* par,struct node* Node)  /*NODE HAVING ONLY ONE CHILD */
{
struct node *temp;
if(Node->left!=NULL)
    temp=Node->left;
else
    temp=Node->right;
if(par==NULL)
    root=temp;
else if(Node==par->left)
    par->left=temp;
else
    par->right=temp;
free(Node);
return root;
}
struct node* CASE3(struct node* root,struct node* par,struct node* Node)  /*NODE HAVE BOTH CHILD */
{
   struct node *succ,*parsucc;
   parsucc=Node;
   succ=Node->right;
   while(succ->left!=NULL)
   {
       parsucc=succ;
       succ=succ->left;
   }
   Node->data=succ->data;
   if(succ->left==NULL&&succ->right==NULL)
       root=CASE1(root,parsucc,succ);
   else
       root=CASE2(root,parsucc,succ);
   return root;
}
struct node* DEL(struct node* root,int val)
{
    struct node *par,*Node;
    Node=root;
    par=NULL;
    while(Node!=NULL)
    {
        if(val==Node->data)
            break;
        par=Node;
        if(val < Node->data)
            Node=Node->left;
        else
            Node=Node->right;
    }
    if(Node==NULL)
        printf("value %d is not present in the tree\n",val);
    else if(Node->left!=NULL&&Node->right!=NULL)
        root=CASE3(root,par,Node);
    else if(Node->left==NULL&&Node->right==NULL)
        root=CASE1(root,par,Node);
    else
        root=CASE2(root,par,Node);
    return root;
}
int LCA_OF_BST(struct node* root,int v1,int v2) //v1 < v2
{
    int data=root->data;
    int x=min(v1,v2),y=max(v1,v2);
    v1=x,v2=y;
    if(root==NULL ||data==v1||data==v2)
        return -1;  //No_Lowest_Common_Ancestor
    else if(data>v1&&data<v2)
        return data;
    else if(data>v1&&data>v2)
        return LCA_OF_BST(root->left,v1,v2);
    else if(data<v1&&data<v2)
        return LCA_OF_BST(root->right,v1,v2);
}
struct node* insertBST(struct node* root,int data)
{
    if(root==NULL)
    {
        root=NEW(data);
        return root;
    }
    else if(root->data>data)
        root->left=insertBST(root->left,data);
    else if(root->data<data)
        root->right=insertBST(root->right,data);
    else
        printf("Duplicate element exist\n");
    return root;
}
void traverseBST(struct node* root,int ttype)   //1.pre_order 2.inorder 3.postorder  ttype :traversal type preorder,postorder,inorder
{    if(root==NULL)
        return ;
    switch(ttype)
    {
        case 1:
            printf("%d ",root->data);
            traverseBST(root->left,1);
            traverseBST(root->right,1);
            break;
        case 2:
            traverseBST(root->left,2);
            printf("%d ",root->data);
            traverseBST(root->right,2);
            break;
        case 3:
            traverseBST(root->left,3);
            traverseBST(root->right,3);
            printf("%d ",root->data);
            break;
    }

}
int LEAFCOUNT(struct node *root)
{
    if(root==NULL)
        return 0;
    if(root->left==NULL&&root->right==NULL)
        return 1;
    return (LEAFCOUNT(root->left)+LEAFCOUNT(root->right));
}
struct Link_list_address_return* THEGREATTREERECURSIONLIST(struct node* root)
{
     struct Link_list_address_return *RET,*RET1,*RET2;
     RET=(struct Link_list_address_return *)malloc(sizeof(struct Link_list_address_return));
     RET1=(struct Link_list_address_return *)malloc(sizeof(struct Link_list_address_return));
     RET2=(struct Link_list_address_return *)malloc(sizeof(struct Link_list_address_return));
     if(root==NULL)
     {
     printf("TREE IS EMPTY\n");
     RET->first=NULL;
     RET->last=NULL;
     return RET;
     }
     if(root->left==NULL&&root->right==NULL)  //leaf node condition
     {
     //RET=(struct Link_list_address_return *)malloc(sizeof(struct Link_list_address_return));
     RET->first=root;
     RET->last=root;
     root->left=root;
     root->right=root;
     // cout<<"leaf \n";
     return RET;
     }
     else if(root->left!=NULL&&root->right==NULL)  //have only left subtree
     {
         //   cout<<"left \n";
            RET1=THEGREATTREERECURSIONLIST(root->left);
        root->left=RET1->last;
        root->right=RET1->first;
        RET1->first->left=root;
        RET1->last->right=root;
        RET1->last=root;
        return RET1;

     }
     else if(root->left==NULL&&root->right!=NULL)  //have only right subtree;
     {

          //  cout<<"right \n";
            RET1=THEGREATTREERECURSIONLIST(root->right);
            root->left=RET1->last;
            root->right=RET1->first;
            RET1->first->left=root;
            RET1->last->right=root;
            RET1->first=root;
                return RET1;

     }
     else if(root->left!=NULL&&root->right!=NULL)  //have both subtree ;
     {
        // cout<<"both before\n";
         RET1=THEGREATTREERECURSIONLIST(root->left);
         RET2=THEGREATTREERECURSIONLIST(root->right);
         root->left=RET1->last;
         root->right=RET2->first;
         RET1->last->right=root;
         RET1->first->left=RET2->last;
         RET2->last->right=RET1->first;
         RET2->first->left=root;
         RET1->last=RET2->last;
        // cout<<"both after\n";
         return RET1;
     }

}
void PRINTDOUBLYLINKLIST(struct node *head,struct node *tail)
{
    if(head==NULL)
    {
            printf("Doubly Link List is empty\n");
        return ;
        }
    else if(head==tail)
    {
        printf("%d ",head->data);
        return ;
    }
    else {
        printf("%d ",head->data);
        PRINTDOUBLYLINKLIST(head->right,tail);
        return ;
    }

}
bool isleaf(struct node *root)
{
   if(root->left==NULL&&root->right==NULL)
   return true;
   return false;
}
bool have_left_child(struct node *root)
{
return !(root->left==NULL);
}
bool have_right_child(struct node *root)
{
return !(root->right==NULL);
}
int childrensumproperty(struct node *root,int increment=0)  //for first call increment=0;
{
    int diff,totalincrement;
    if(isleaf(root))
    {
       // cout<<"leaf";
       root->data+=increment;
       return 0;
    }
    root->data+=increment;
    diff=root->data-(have_left_child(root)?root->left->data:0)-(have_right_child(root)?root->right->data:0);
    if(diff==0)  //case 1:
    {
        totalincrement=(have_left_child(root)?childrensumproperty(root->left):0)+(have_right_child(root)?childrensumproperty(root->right):0);
         root->data+=totalincrement;
         return totalincrement;
    }
    else if(diff<0)
    {
        root->data-=diff;  //to add the difference bcz diff is negative so -diff is > 0
        totalincrement=(have_left_child(root)?childrensumproperty(root->left):0)+(have_right_child(root)?childrensumproperty(root->right):0);
         root->data+=totalincrement;
         totalincrement-=diff;
         return totalincrement;
    }
    else if(diff > 0 )
    {
        //case 1 for left child increment only
        if(have_left_child(root))
        {
        totalincrement=(have_left_child(root)?childrensumproperty(root->left,diff):0)+(have_right_child(root)?childrensumproperty(root->right):0);
       // root->data+=(have_left_child(root)?childrensumproperty(root->left,diff):0)+(have_right_child(root)?childrensumproperty(root->right):0);
        root->data+=totalincrement;
        }
        else if(have_right_child(root))
        {
        totalincrement=(have_left_child(root)?childrensumproperty(root->left):0)+(have_right_child(root)?childrensumproperty(root->right,diff):0);
       //root->data+=(have_left_child(root)?childrensumproperty(root->left):0)+(have_right_child(root)?childrensumproperty(root->right,diff):0);
        root->data+=totalincrement;
        }
        return totalincrement;
    }
  
  
}
int Diameter_of_Tree(struct node *root,int *height)
{
/*complexity is O(n) */
    int lh=0,rh=0;
    int ld=0,rd=0;
    if(root==NULL)
        {
        *height=0;
        return 0;
        }
    ld=Diameter_of_Tree(root->left,&lh);
    rd=Diameter_of_Tree(root->right,&rh);
    *height=max(lh,rh)+1;
    return max(lh+rh+1,max(ld,rd));
}
bool isAVL(struct node *root,int *height)
{
bool b1,b3,b2=false;
int lh,rh;
      if(root==NULL)
      {
      *height=0;
      return true;
      }
      b1=isAVL(root->left,&lh);
      if(b1==false)
      return false;
      b2=isAVL(root->right,&rh);
      if(b2==false)
      return false;
      *height=max(lh,rh)+1;
      if(abs(lh-rh)>=2)
      return false;
      else
      return true;
}
/*
Total number of possible Binary Search Trees with n keys = Catalan number Cn = (2n)!/(n+1)!*n!
*/
struct node* Mirror(struct node* root)
{
     struct node *temp;
     if(root==NULL)
     return NULL; //for NULL
     temp=root->left;
     root->left=root->right;
     root->right=temp;
     root->left=Mirror(root->left);
     root->right=Mirror(root->right);
     return root;
}
bool isStructSame(struct node *r1,struct node* r2)
{
      if(r1==NULL&&r2==NULL)
      return true;
      if(r1!=NULL&&r2!=NULL&&isStructSame(r1->left,r2->left)&&isStructSame(r1->right,r2->right))
      return true;
      return false;
}
void isFoldable(struct node* root)
{
/*
   A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable.
*/
    if(root==NULL)
        {
            cout<<"Tree is Foldable\n";
            return ;
        }
    root->left=Mirror(root->left);   // get Mirror image of left subtree
    bool flag=isStructSame(root->left,root->right);
    root->left=Mirror(root->left);  //to change the tree before mirror is Inverse Mirror
    if(flag)
        {
                cout<<"Tree is Foldable\n";
            return ;  
        }
    else
        {
                cout<<"Tree is Not Foldable\n";
            return ;
        }
//if flag is False then not foldable else flodable
return ;
}
struct node* Make_Bst(struct node* root)
{
     printf("Enter number of elements to insert in tree \n");
     int n,data;
     cin>>n;
     for(int i=0;i<n;i++)
     {
        cout<<"enter the value u want to push in the tree \n";
        cin>>data;
        root=insertBST(root,data);
     }
     return root;
}
struct node* make_test_tree(struct node *root)
{
      root=NEW(10);
      root->left=NEW(7);
      root->right=NEW(15);
      root->left->left=NEW(5);
      root->right->left=NEW(11);
      return root;
    
}
struct node* minvalue(struct node *root)
{

        if(root==NULL)
        {
           printf("No minimum value exist");
           return NULL;
        }
        cout<<root->data<<" \n ";
        if(root->left==NULL)
        {
           cout<<"hi i m";
           printf("Minimum value is %d",root->data);
           return root;
        }
        if(root->left!=NULL)
        {
           while(root->left!=NULL)
           {
             root=root->left;
           }
           printf("Minimum value is %d",root->data);
           return root;
        }
}
struct node* inorderSuccessor(struct node* root,struct node* Node)
{
    struct node *succ;
      if(Node->right!=NULL)
       {
       cout<<"hi"<<Node->data<<" ";
       succ=minvalue(Node->right);
       return succ;
       }
       succ=NULL;
       while(root!=NULL)
       {
            if(Node->data<root->data)
            {
            succ=root;
            root=root->left;
            }
            else if(Node->data > root->data)
                root=root->right;
            else
                break;
              
       }
       return succ;
}
int Kth_smallest_element(struct node* root,int k)
{
    int pop_count=0;
    stack <struct node*> S;
    if(root==NULL)
    {
        printf("No element in the Binary Search Tree\n");
        return -1;  //on error
    }   //NO result
    S.push(root);
    struct node *temp1;
    temp1=root;
    while(!S.empty())
    {
          if(temp1->left!=NULL)
          {
              while(temp1->left!=NULL)
              {
                  S.push(temp1->left);
                  temp1=temp1->left;
              }
          }
          else
          {
              temp1=S.top();
              S.pop();
              pop_count++;
              if(pop_count==k)
              return temp1->data;
              while((!S.empty())&&temp1->right==NULL)
              {
                  temp1=S.top();
                  S.pop();
                  pop_count++;
                  if(pop_count==k)
                     return temp1->data;
              }
              if(temp1->right!=NULL)
              {
                  S.push(temp1->right);
                  temp1=temp1->right;
              }
             
          }
    }
  
    printf("\nError : The number of Nodes in the BST in less than K\n");
    return -1;
}
int level_of_node(struct node* root,int key,int level=1)
{
/* this function works for any Binary Tree not only for BST*/
    if(root==NULL)
        return 0;
    if(root->data==key)
        return level;
    return level_of_node(root->left,key,level+1) | level_of_node(root->right,key,level+1);
}
bool printAll_Ancestor(struct node* root,int key)
{
  if(root==NULL)
  return false;
  if(root->data==key)
  return true;
  if( printAll_Ancestor(root->left,key)||printAll_Ancestor(root->right,key))
  {
      printf("%d ",root->data);
      return true;
  }
  return false;
}
void print_keys_in_range(struct node *root,int k1,int k2)   //k1<=key<=k2  valid for BST
{
   if(root==NULL)
   return ;
   if(root->data>k1)
      print_keys_in_range(root->left,k1,k2);
   if(root->data>=k1&&root->data<=k2)
      printf("%d ",root->data);
   if(k2>root->data)
      print_keys_in_range(root->right,k1,k2);
   return ;
}
int main()
{
int height=0;
struct node* root=NULL;
struct node *r1=NULL,*r2=NULL;
//root=insertBST(root,2);
/*root=insertBST(root,15);
root=insertBST(root,10);
root=insertBST(root,8);
root=insertBST(root,16);
root=insertBST(root,17);*/
root=Make_Bst(root);
traverseBST(root,2);
//print_keys_in_range(root,1,35);
//printf("\n")&&printAll_Ancestor(root,4);
//cout<<"\n"<<Kth_smallest_element(root,18)<<endl;
//cout<<"\nLevel of the key :"<<level_of_node(root,13)<<endl;
//root=make_test_tree(root);
//isFoldable(root);
//struct Link_list_address_return *RET;
//root=DEL(root,1);
//r1=Make_Bst(r1);
//r2=Make_Bst(r2);
//traverseBST(root,2);
//root=Mirror(root);
//cout<<LCA_OF_BST(root,3,5);
//childrensumproperty(root);
//cout<<"\n";
//traverseBST(root,1);
//cout<<"\n Inorder Successor :"<<inorderSuccessor(root,root->left)->data<<"\n";
//cout<<"\n Diameter of Tree :"<<Diameter_of_Tree(root,&height);
//RET=THEGREATTREERECURSIONLIST(root);
//PRINTDOUBLYLINKLIST(RET->first,RET->last);
return 0;
}

Implementation of banker's algorithm in c++

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define s(x) printf("\n%s\n",x);
#define p(x) printf("%d\n",x);
#define ss(a) scanf("%d",&a);
#define f(a,b) for(int i=0;<a;i++) \
                   for(int j=0;j<b;j++)
#define ff(a) for(int i=0;i<a;i++)
int main()
{
int _max[5][5]={0};
int a_lc[5][5]={0};
int _ned[5][5]={0};
int res[5]={0};
int re_v[5]={0};
s("enter max table")
//f(0,5)
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
ss(_max[i][j])
s("enter allocation table")
//f(0,5)
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
ss(a_lc[i][j])
//f(0,5)
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
_ned[i][j]=_max[i][j]-a_lc[i][j];
s("enter available resource vector")
ff(5)
ss(res[i])
s("enter request vector");
ff(5)
ss(re_v[i])
ff(5)
{
if(re_v[i]>res[i])
{
puts("error");
return 0;
}
}
// now check for saftey algo
ff(5)
{
res[i]=res[i]-re_v[i];
}
int counter=10;
bool finish[5]={false};
while(counter--)
{
    for(int i=0;i<4;i++)
     {
     int flag=false;
       if(finish[i])
        continue;
        for(int j=0;j<4;j++)
        {
              flag=true;
              if(res[j]<_ned[i][j])
              {
              flag=false;
              break;
              }
        }
          finish[i]=true;
          if(finish[i]==true)
          {
          for(int l=0;l<4;l++)
          res[l]+=a_lc[i][l];
          }
     }
}
for(int i=0;i<4;i++)
if(finish[i]==false)
{
printf("unsafe state\n");
return 0;
}
printf("safe state\n");
return 0;
}

LEET CODE PROBLEM :-Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

 class Solution {
public:
    bool isPalindrome(string s) {
        int l=s.length();
        char a1[l],c1=0;
        for(int i=0;i<l;i++)
    if((s.at(i)>=97&&s.at(i)<=122)||(s.at(i)>=65&&s.at(i)<=90)||(s.at(i)>=48&&s.at(i)<=57))
        {
                   a1[c1++]=s.at(i);
                   if(s.at(i)>=97)
                   a1[c1-1]-=32;
        }
                   a1[c1]='\0';
        int l1=0,h=c1-1;
        char a2[c1];
    for(int i=0,j=c1-1;i<c1;i++,j--)
         a2[i]=a1[j];
         a2[c1]=0;
    if(!strcmp(a1,a2))
    return true;
    return false;
}
};                                                                                                                                               

MATRIX MULTIPLICATION USING PIPES

CODE SNIPPET IS HERE PLEASE WRITE COMMENT 'S FOR ANY MODIFICATION
        #include<unistd.h>
#include<stdio.h>
#include<sys/stat.h>
#define P(X) for(l=0;l<2;l++){\
                 for(m=0;m<2;m++)\
                        printf("%d ",X[l][m]); printf("\n");}\

#define S(X) for(l=0;l<2;l++){\
                 for(m=0;m<2;m++)\
                        scanf("%d",&X[l][m]);}\

int main()
{
    int l,m,n;
    int pid;
    int p1[2],p2[2];
    pipe(p1);
    pipe(p2);

            if((pid=fork())==0)
                   {
              
                           int mat1[2][2]={1,2,3,4};
                           int mat2[2][2]={{1,2},{2,3}};
                            P(mat1);
                         P(mat2);
                 
                           int ans[2][2];
    
                           write(p1[1],mat1,2*2*sizeof(int));
                           write(p2[1],mat2,2*2*sizeof(int));
       
       
                           read(p1[0],ans,2*2*sizeof(int));
                           P(ans);
            
                   }
                else
                   {
                           int mul[2][2]={0},m1[2][2],m2[2][2],i,j,k;
 
                           read(p1[0],m1,2*2*sizeof(int));
                           read(p2[0],m2,2*2*sizeof(int));
                           P(m1);
                           P(m2);
                           for(i=0;i<2;i++)
                                 for(j=0;j<2;j++)
                                          for(k=0;k<2;k++)
                                              mul[i][j]+=m1[i][k]*m2[k][j];
           
                           P(mul);
                           write(p1[1],mul,2*2*sizeof(int));
             
            
                    }
return 0;
}

CHECK WHEN YOU HAVE NO EFFICIENT MEMORY TO ALLOCATE

There is a header new in c++ which have a function set_new_handler()
it run when " new " doesn't allocate memory
you can check it with the help of following program
#include<iostream>
#include<new>
#include<cstdlib>
using namespace std;
int count=0;
void out_of_memory()
{
    cerr<<"memory exhausted after"<<count<<"allocations!"<<endl;
    exit(1);
}
int main()
{
set_new_handler(out_of_memory);
while(1)
{
    count++;
    new int[10000];
}
return 0;
}

output:---

kruskal algorithm code snippet of MST

#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#include<utility>
using namespace std;
vector< pair< pair < int,int > ,int > > edge,ans;   //edge x,y,weight
map< int, vector<int> > group;    //groupno --> groupelement
vector<int> node(1001,0);   //number of nodes maximum 1000;
bool comp(pair< pair <int,int > ,int > A,pair< pair <int ,int > ,int > B)
{
    if(A.second< B.second)
        return true;
    else
        return false;
}
int main()
{
    int cgroup=1,m;
    int n,x,y,w,e=0;
    cin>>n>>m;  //m - no of nodes
    for(int i=0;i<n;i++)
    {

        cin>>x>>y>>w;
        edge.push_back(make_pair(make_pair(x,y),w));

    }

    sort(edge.begin(),edge.end(),comp);
    int k=0;
    while(e<n-1)
    {
        x=edge[k].first.first,y=edge[k].first.second,w=edge[k].second;
        if(node[x]==0&&node[y]==0)
        {
              ans.push_back(make_pair(make_pair(x,y),w));
                      group[cgroup].push_back(x);
              group[cgroup].push_back(y);
              node[x]=cgroup;
              node[y]=cgroup;
              cgroup++;
              e++;
        }
        else if(node[x]!=0&&node[y]!=0)
        {
                    if(node[x]>node[y])
                          {
                  ans.push_back(make_pair(make_pair(x,y),w));

                  e++;
                  int tempgrp=node[y];
                  node[y]=node[x];
                        for(int i=0;i<group[tempgrp].size();i++)
                  {
                      int elem=group[tempgrp][i];
                      node[elem]=node[x];
                      group[node[x]].push_back(elem);
                  }
               
                }
            else if(node[x]<node[y])
            {
                ans.push_back(make_pair(make_pair(x,y),w));

                e++;
                int tempgrp=node[x];
                node[x]=node[y];
                for(int i=0;i<group[tempgrp].size();i++)
                {
                    int elem=group[tempgrp][i];
                    node[elem]=node[y];
                    group[node[y]].push_back(elem);
                }
           
            }
        }
        else if(node[x]!=0&&node[y]==0)
        {
            ans.push_back(make_pair(make_pair(x,y),w));

            e++;
            int tempgrp=node[x];
            group[tempgrp].push_back(y);
            node[y]=node[x];
        }
        else if(node[x]==0&&node[y]!=0)
        {
            ans.push_back(make_pair(make_pair(x,y),w));

            e++;
            int tempgrp=node[y];
            node[x]=node[y];
            group[tempgrp].push_back(x);
        }

             k++;
    }
    int grp=node[1];
    for(int i=0;i<ans.size();i++)
        cout<<ans[i].first.first<<" "<<ans[i].first.second<<" "<<ans[i].second<<endl;
       


}

KMP - algorithm for string matching
complexity of compute prefix function O(m) ,where m is length of the pattern
complexity of KMP is O(n)
Reference-Coreman 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int pie[500];
char *pattern;
char *text;
int m;  //length is pattern
int n;  //length of text
void compute_prefix()
{
    cin>>pattern+1;
    cin>>text+1;
     m=strlen(pattern+1);
    int k=0;
    pie[1]=0;
    for(int q=2;q<=m;q++)
    {
        while(k>0&&pattern[k+1]!=pattern[q])
        {
            k=pie[k];
          
        }
        if(pattern[k+1]==pattern[q])
            k=k+1;
        pie[q]=k;

    }
}
void kmp_matching()
{

     compute_prefix();
     n=strlen(text+1);
     int q=0;
     for(int i=1;i<=n;i++)
     {
         while(q>0&&pattern[q+1]!=text[i])
         {
             q=pie[q];
         }
         if(pattern[q+1]==text[i])
             q=q+1;
         if(q==m)
         {
             printf("pattern occurs with shift %d\n",i-m);
             q=pie[q];
         }
     }

}

int main()
{

    pattern=new char[500];
    text=new char[1000];
        kmp_matching();
    return 0;
}

Matrix_exponential Template use for solving recurrence relation

/* Template of matrix exponential written by Rahul Kumar Singh (selfcompiler) date :19-oct-2012 time --8:41 P.M. */
/* ~~~~~~~~**@#*#@**~~~~~~~~~*/
#include<cstdio>
#include<iostream>
#include<math.h>
#include<vector>
#include<utility>
#include<map>
using namespace std;
#define K 3 
//size of matrix using 1 based index not 0'!!!!! ........
#define LIMIT 10000000000000
//maximum value of n
#define MODULO 1000000007
// modulo value
#define ll long long int
/*matrix structure */
struct MATRIX{
        ll mat[K+1][K+1];
    MATRIX()  //constructor
    {
        for(int i=0;i<=K;i++)
            for(int j=0;j<=K;j++)
                mat[i][j]=0;
    }//end constructor
    void print_matrix() //print matrix
    {
        for(int i=1;i<=K;i++)
        {
            for(int j=1;j<=K;j++)
                cout<<mat[i][j]<<" ";
            cout<<std::endl;
        }
    } //end print matrix

};//end of matrix structre
/* main program start here */
int main()
{
    struct MATRIX A;  
    ll column[K+1]={0,1,1,1};  //column vector to find the answer
    A.mat[1][1]=1,A.mat[1][2]=1,A.mat[1][3]=1;  //transformation matrix of 3 X 3 (1 based index)
    A.mat[2][1]=1,A.mat[2][2]=0;A.mat[2][3]=0;
    A.mat[3][1]=0,A.mat[3][2]=1,A.mat[3][3]=0;
    map<int,struct MATRIX> I;
    I[1]=A;  //transformation matrix
        ll next=2,p=1,p1,p2;
while(next<=LIMIT)    //precomputation of matrix of power 1,2,4,8,16,.......
{
             MATRIX object;
         p1=p2=p;
         for(int i=1;i<=K;i++)    //matrix multiplication start
         for(int j=1;j<=K;j++)
             for(int k=1;k<=K;k++)
             {
                  object.mat[i][j]+=(I[p1].mat[i][k]*I[p2].mat[k][j])%MODULO;
                  if(object.mat[i][j]>=MODULO)
                           object.mat[i][j]%=MODULO;

             }//matrix multipliaction end
         I[next]=object;
         p=next;
         next=next*2;
               
}//end of precomputation
    ll tc,n,count=0,pw2;
    cin>>tc;
    ll term[K+1]={0,1,1,1};     //r=q+w+e;   //term[1]>term[2]>term[3];
while(tc--)
{
    cin>>n;
    MATRIX obj;
        count=1;
                if(n>=4)
        {
        n=n-3;
        while(n)  //compute matrix of power n
        {


                     ll x=n&-n;  //farthest set bit of n
                          if(count)  
              {      //first encounter for initialization
                                 count=0;  
                 obj=I[x];

              }
              else
              {
                    MATRIX temp;  //make a temp object
                 for(int i=1;i<=K;i++)// matrix multipliaction
                 for(int j=1;j<=K;j++)
                     for(int k=1;k<=K;k++)
                         {
                           temp.mat[i][j]+=(I[x].mat[i][k]*obj.mat[k][j])%MODULO;
                           if(temp.mat[i][j]>=MODULO)
                           temp.mat[i][j]%=MODULO;
                         }//matrix multipliaction end
                obj=temp;
              }
              n=n-x;
        ll ans=0;
        for(int i=1;i<=K;i++)  //compute answer
        {
            ans+=(column[i]*obj.mat[1][i])%MODULO;
            if(ans>=MODULO)
                ans%=MODULO;
        }// finally computed
             cout<<ans<<std::endl;
        }
        else
        {
            cout<<term[n]<<std::endl;
        }

}

         return 0;
}

   
 // complexity O(logN)

CLASSIFIACTION OF EDGES IN GRAPH 

EDGES OF A DIRECTED GRAPH CAN BE DIVIDE INTO FOUR GROUPS 

1.Tree Edge 

2.Back Edge 

3.Forward Edge 

4.Cross Edge                

TREE EDGE :

an edge included in the DFS spanning forest.

BACK EDGE :

an edge to a vertex to its spanning tree ancestor.  

FORWARD EDGE :

an edge from a vertex to a spanning tree non son descendant.

CROSS EDGE :

an edge between two vertices is a cross edge when there is no ancestor and descendant relationship between them in spanning forest.

code to identify the edges

static int time=0;

void DFS(int v)

{

int i;

time++;

d[v]=time;

state[v]=visited;

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

{

     if(adj[v][i]==1)

       {

          if(state[i]==initial)

              {

              cout<<"Tree Edge :"<<v<<" "<<i<<"\n";

              DFS(i);

               }

            else if(state[i]==visited)

               { 

                   cout<<"Back Edge :"<<v<<" "<<i<<"\n";    

                }

              else if(d[v]<d[i])

                  cout<<"Forward Edge :"<<v<<" "<<i<<"\n";

                else

                  cout<<"Cross Edge :"<<v" "<<i<<"\n";

              }

     }

state[v]=finished;

  f[v]=++time;

return ;

}

THIS IS DEPTH FIRST SEARCH (WAY TO TRAVERSE A GRAPH)  DFS!!!!!!!!!!
THERE IS TWO APPROACHES TO DO IT 
1:- ITERATIVE APPROACH
2:-RECURSIVE APPROACH 
APPLICATION:- FINDING CONNECTED COMPONENTS
           :-TOPOLOGICAL SORTING
           :-FINDING BRIDGE ON A GRAPH
           :-FIND STRONGLY CONNECTED COMPONENTS
           :-FINDING BICONNECTIVITY IN GRAPH
   LINK TO STUDY :-DFS wiki link

CODE OF ITERATIVE APPROACH 
#include<iostream>
#include<stack>
#include<vector>
#include<stdio.h>
using namespace std;
#define MAX 100
#define initial 1
#define visited 2
int n;/* number of nodes in the graph*/
int adj[MAX][MAX]; //adjancency matrix
int state[MAX]; /*can be visited or initial*/
stack<int> stac_k;
void create_graph()   //create a graph //
{
int i,o,d,max_edge;
printf("enter the number of nodes\n");
scanf("%d",&n);
max_edge=n*(n-1);
       for(i=1;i<=max_edge;i++)
         {
          printf("enter the edge %d:(-1,-1 to quit) ",i);
          scanf("%d%d",&o,&d);
          if((o==-1)&&(d==-1))
          break;
          if((o>=n)||(d>=n)||(o<0)||(d<0))
          {cout<<"invalid edge";i--;}
          else
          adj[o][d]=1;
         }
return ;
}
void display_graph()  //display graph
{
           for(int i=0;i<n;i++)
           {
           for(int j=0;j<n;j++)
           {
           if(adj[i][j]==1)
           cout<<"1";
           else
           cout<<"0";
           }
           cout<<endl;
           }
return;
}
void DFS(int v)
{
  int i;
  stac_k.push(v);
  while(!stac_k.empty())
   {
     v=stac_k.top();
        stac_k.pop();
               if(state[v]==initial)
              {
                   state[v]=visited;
                   cout<<v<<":->";
               }
               for(i=n-1;i>=0;i--)
              {
                   if((state[i]==initial)&&(adj[v][i]==1))
                   stac_k.push(i);
              }
  }
return ;
}
void df_traversal()
{
   int v=0;
   for(v=0;v<n;v++)
    state[v]=initial;
   printf("enter starting vertex for DFS\n");
   scanf("%d",&v);
   DFS(v);
return ;
}
int main()
{
create_graph();
display_graph();
df_traversal();
return 0;
}

well this is my first blog !!! 
first :-my name:- RAHUL SINGH
myintrest:-coding,take participation in programming contest;
what topics i discuss here untill the end is algorithms,programming questions ,data structures,c,c++ 
MY CODECHEF PROFILE