String Formatting Question - Smartprix Coding Test

Replacement Array is an array of elements.
Format String contains conversion specifier %s, followed by optional index specifier [1], followed by optional length specifier :3.
Format String: %s[1]:3
%s is conversion specifier - mark the starting of conversion string
[1] is index specifier - corresponding index of Replacement Array
:3 is length specifier - number of characters to be taken from string



The replacement works as follows:
Example:
Replacement Array: Smart site India comparison Best
Format String: %sprix is the %s[4] online %s[3]:6 shopping %s:9 in %s
Output: Smartprix is the Best online compar shopping site in India.
If no index specifier is present with conversion specifier %s, Index 0, 1, 2, 3... are assigned to all in sequence from left to right.
In above example %sprix is %s[0]prix; %s:9 is %s[1]:9 and so on.
The specifier string is replaced by element of Replacement Array denoted by index specifier. If no element is found the specifier is not replaced.
In above example %s[4] is replaced by element at 4th index of the Replacement Array "Best". %sprix is replaced by Smartprix and so on.
%s[3]:6 is replaced by 'first 6 characters' of the element at 3rd index of the Replacement Array, i.e., "compar".
If the 'length specifier' is not present or is greater than length of the element then use whole string.
%s:9 is replaced by site, %s[4] is replaced by Best.
For any error case, specifier is not replaced.



Input:
There will be 2 lines in the input.
1st line contains space separated elements of Replacement Array
2nd line is Format String



Output:
Formatted String



INPUT 1
smart site india comaprision best
%sprix is the %s[4] online %s[3]:6 shopping %s:9 in %s
OUTPUT
smartprix is the best online comapr shopping site in india


INPUT 2
india boom startup up hub
%s %s[is] a %sing %s:5%s:5 %s[4]. and %s[6] are :4 of %s[-1].
OUTPUT
india %s[is] a booming startup hub. and %s[6] are :4 of %s[-1].


INPUT 3
hello lavish kothari
%s[2]:xyz
OUTPUT
%s[2]:xyz

#include<bits/stdc++.h>
using namespace std;

int findCase(string &b,int index)
{
    if(index+2>=b.size())
        return 1;
    /*
    if(b[index+2]!=':' && b[index+2]!='[')
        return 1;
    */
    
    if(b[index+2]==':' && index+3<b.size() && b[index+3]>='0' && b[index+3]<='9')
        return 4;
    if(b[index+2]==':')
        return 0;
    
    if(b[index+2]=='[')
    {
        int i=index+3;
        if(i>=b.size() || b[i]<='0' || b[i]>='9')
            return 0;
        while(i<b.size() && b[i]>='0' && b[i]<='9')
            i++;
        if(i==b.size())
            return 0;           // for case %s[1234
        else if(b[i]==']')
        {
            if(i+1>=b.size() || b[i+1]!=':')
                return 2;
            else if(b[i+1]==':')
            {
                if(i+2>=b.size())
                    return 0;
                else if(b[i+2]>='0' && b[i+2]<='9')
                    return 3;
                else
                    return 0;
            }
        }
        else return 1;
    }
    return 1;
}
int extract(string &b,int index)
{
    int sum=0;
    while(index<b.size() && b[index]>='0' && b[index]<='9')
    {
        sum=sum*10+b[index]-'0';
        index++;
    }
    return sum;
}
void findFormattedString(string &a,string &b)
{
    vector<string>vs;
    int start=0;int len=0;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]==' ')
        {
            vs.push_back(a.substr(start,len));
            while(i<a.size() && a[i]==' ')
                i++;
            start=i;
            len=0;
        }
        len++;
    }
    if(a[a.size()-1]!=' ')
        vs.push_back(a.substr(start,a.size()-start));
    
    /*
    for(int i=0;i<vs.size();i++)
        cout<<"**"<<vs[i]<<endl;
    */
    int counter=0,startfrom=0;
    while(1)
    {
        int index=b.find("%s",startfrom);
        if(index<0)
            break;
        int c=findCase(b,index);
        if(c==1)
        {
            if(counter>=vs.size())
            {
                startfrom=index+1;
                continue;
            }
            b.erase(b.begin()+index,b.begin()+index+2);
            b.insert(index,vs[counter]);
            counter++;
        }
        else if(c==2)
        {
            int number=extract(b,index+3);
            if(number<0 || number>=vs.size())
            {
                startfrom=index+1;
                continue;
            }
            int i=index+3;
            while(i<b.size() && b[i]>='0' && b[i]<='9')
                i++;
            b.erase(b.begin()+index,b.begin()+i+1);
            b.insert(index,vs[number]);
        }
        else if(c==3)
        {
            int number1=extract(b,index+3);
            if(number1<0 || number1>=vs.size())
            {
                startfrom=index+1;
                continue;
            }
            int i=index+3;
            while(i<b.size() && b[i]>='0' && b[i]<='9')
                i++;
            b.erase(b.begin()+index,b.begin()+i+2);
            
            int number2=extract(b,index);
            i=index;
            while(i<b.size() && b[i]>='0' && b[i]<='9')
                i++;
            b.erase(b.begin()+index,b.begin()+i);
            
            if(vs[number1].size()<=number2)
            {
                b.insert(index,vs[number1]);
            }
            else 
                b.insert(index,vs[number1].substr(0,number2));
        }
        else if(c==4)
        {
            if(counter>=vs.size())
            {
                startfrom=index+1;
                continue;
            }
            int number=extract(b,index+3);
            int i=index+3;
            while(i<b.size() && b[i]>='0' && b[i]<='9')
                i++;
            b.erase(b.begin()+index,b.begin()+i);
            if(vs[counter].size()<=number)
            {
                b.insert(index,vs[counter++]);
            }
            else 
                b.insert(index,vs[counter++].substr(0,number));
        }
        else if(c==0)
            startfrom=index+1;
    }
}
int main()
{
    string a,b;
    getline(cin,a);
    getline(cin,b);
    findFormattedString(a,b);
    cout<<b<<endl;
    return 0;
}

Water Jug Problem (Oracle Interview)

This problem was asked to me during my Oracle interview. The interviewer asked me to write down the code for the same.
 
Problem :

You are given three water jugs.
Let the capacity of jugs be X, Y and Z. (X >= Y >= Z).
As described in all common water jug problems, neither of the jugs has any measuring markers on it.

Initially we have only the first jug (with capacity X) fully filled up to brim (the other two jugs are initially empty).
Now you need to tell whether it is possible or not to transfer the water, in such a way that you reach to a state in which any two jugs have equal amount of water in them, and the third jug is empty.
In short, you have to divide X litre of water into two equal halves. These two equal halves can be in any of the two jugs.

Example
Suppose, X=10, Y=7, Z=3
Solution steps:
10 0 0 -> Initial State
3 7 0
0 7 3
7 0 3
7 3 0
4 3 3
4 6 0
1 6 3
1 7 2
8 0 2
8 2 0
5 2 3
5 5 0 -> Final State


C++ Program to solve this problem :

#include<bits/stdc++.h>
using namespace std;
class triplet
{
    public:
    int x,y,z;
    triplet(int x,int y,int z)
    {
        this->x=x;
        this->y=y;
        this->z=z;
    }
    
};
bool findTriplet(vector<triplet>&v,int x,int y,int z)
{
    for(int i=0;i<v.size();i++)
        if(v[i].x==x && v[i].z==z && v[i].y==y)
            return true;
    return false;
}
bool getSteps(int x,int y,int z,int X,int Y,int Z) // x y and z denotes the current capacity.
{
    static vector<triplet>v;
    if(findTriplet(v,x,y,z))
        return false;
    else 
        v.push_back(triplet(x,y,z));
    cout<<x<<" "<<y<<" "<<z<<endl;
    if(x==y && z==0)
        return true;
    if(z==y && x==0)
        return true;
    if(x==z && y==0)
        return true;
    
    /*********************************--> transferring from X <--*****************************************************/        
    if(x>0)
    {
        // transferring from x to y
        {
        int emptyy=Y-y;
        int newx,newy;
        if(emptyy>=x)
        {
            newy=y+x;
            newx=0;
        }
        else
        {
            newy=Y;
            newx=x-emptyy;
        }
        if(emptyy>0 && getSteps(newx,newy,z,X,Y,Z))
            return true;
        }
    
        // transferring from x to z
        {
        int emptyz=Z-z;
        int newx,newz;
        if(emptyz>=x)
        {
            newz=z+x;
            newx=0;
        }
        else
        {
            newz=Z;
            newx=x-emptyz;
        }
        if(emptyz>0 && getSteps(newx,y,newz,X,Y,Z))
            return true;
        }
    }
            
    /*********************************--> transferring from Y <--*****************************************************/        
    if(y>0)
    {
        // transferring from y to x
        {
        int emptyx=X-x;
        int newx,newy;
        if(emptyx>=y)
        {
            newx=x+y;
            newy=0;
        }
        else
        {
            newx=X;
            newy=y-emptyx;
        }
        if(emptyx>0 && getSteps(newx,newy,z,X,Y,Z))
            return true;
        }
    
        // transferring from y to z
        {
        int emptyz=Z-z;
        int newy,newz;
        if(emptyz>=y)
        {
            newz=z+y;
            newy=0;
        }
        else
        {
            newz=Z;
            newy=y-emptyz;
        }
        if(emptyz>0 && getSteps(x,newy,newz,X,Y,Z))
            return true;
        }
    }
            
    /*********************************--> transferring from Z <--*****************************************************/        
    if(z>0)
    {
        // transferring from z to y
        {
        int emptyy=Y-y;
        int newz,newy;
        if(emptyy>=z)
        {
            newy=y+z;
            newz=0;
        }
        else
        {
            newy=Y;
            newz=z-emptyy;
        }
        if(emptyy>0 && getSteps(x,newy,newz,X,Y,Z))
            return true;
        }
    
        // transferring from z to x
        {
        int emptyx=X-x;
        int newz,newx;
        if(emptyx>=z)
        {
            newx=z+x;
            newz=0;
        }
        else
        {
            newx=X;
            newz=z-emptyx;
        }
        if(emptyx>0 && getSteps(newx,y,newz,X,Y,Z))
            return true;
        }
    }
    return false;
}
int main()
{
    int x,y,z;
    cin>>x>>y>>z;
    if(getSteps(x,0,0,x,y,z))
        cout<<"Yes!! you got a solution!!"<<endl;
    else cout<<"No solution found!!"<<endl;
    return 0;
}

Please write comments if you find anything incorrect, or you want to share more information about the problem discussed above.

Reverse a Linked List in groups of given size

#include<stdio.h>
#include<stdlib.h>

struct node {
	int value;
	struct node* next;
};

struct node* createnode(int no) {
	
	struct node*temp;
	
	temp = (struct node*)malloc(sizeof(struct node*));
	temp->value = no;
	temp->next = NULL;

	return temp;
}

struct node * insert(struct node*  head, int no) {

	struct node *temp, *headcp;
	temp = createnode( no);

	if(head == NULL)
		return temp;


	headcp = head;
	
	while(head->next != NULL) {
		head = head->next;
	}
	head->next = temp;
	return headcp;
}

void print (struct node*  head) {

	while(head != NULL) {
		printf("%d -> ",head->value);
		head = head->next;
	}


}
struct node*reverse(struct node*head,int k)
{
	int counter=0;
	struct node*current,*prev,*nxt;
	if(head==NULL || head->next==NULL)
		return head;
	prev=NULL;
	current=head;
	nxt=head->next;
	while(current && counter!=k)
	{
		current->next=prev;
		prev=current;
		current=nxt;
		if(nxt)
			nxt=nxt->next;
		counter++;
	}
	return prev;
}

struct node*reverseInBlocksIterative(struct node*head,int k)
{
	struct node*ret,*newhead,*prev,*current,*last;
	int counter=0,i;
	if(k==1 || !head || !(head->next))
		return head;
	
	for(i=0,ret=head;i<k-1 && ret;i++)
		ret=ret->next;
	if(!ret)
		return reverse(head,k);
	
	current=head;
	prev=head;
	last=NULL;
	while(current)
	{
		for(i=0;i<k && current;i++)
			current=current->next;
		newhead=reverse(prev,k);
		prev=current;
		if(last)
			last->next=newhead;
		while(newhead->next)
			newhead=newhead->next;
		last=newhead;
	}
	return ret;
}

struct node*reverseInBlocksRecursive(struct node*head,int k)
{
	int i;
	struct node*current,*ptr,*ret;
	if(!head)
		return NULL;
	for(i=0,current=head;i<k && current;i++)
		current=current->next;
	ret=reverse(head,k);
	for(ptr=ret;ptr->next;ptr=ptr->next);
	ptr->next=reverseInBlocksRecursive(current,k);
	return ret;
}

int main () {

	struct node*head=NULL;
	head = insert(head, 1);	
	head = insert(head, 2);	
	head = insert(head, 3);	
	head = insert(head, 4);	
	head = insert(head, 5);	
	head = insert(head, 6);	
	head = insert(head, 7);	
	head = insert(head, 8);			
	head = insert(head, 9);			
	head = insert(head, 10);			
	head = insert(head, 11);			
	head = insert(head, 12);			

	int k;
	scanf("%d",&k);
	head = reverseInBlocksRecursive(head, k);
	print(head);

	return 0;
}

Snakes and Ladders - Codechef - Solution

Problem Statement:
Bhuvesh takes out his Snakes and Ladders game and stares at the board, and wonders: If he had absolute control on the die, and could get it to generate any number (in the range 1-6) he desired, what would be the least number of rolls of the die in which he'd be able to reach the destination square (Square Number 100) after having started at the base square (Square Number 1)?

Rules

Bhuvesh has total control over the die and the face which shows up every time he tosses it. You need to help him figure out the minimum number of moves in which he can reach the target square (100) after starting at the base (Square 1).
A die roll which would cause the player to land up at a square greater than 100, goes wasted, and the player remains at his original square. Such as a case when the player is at Square Number 99, rolls the die, and ends up with a 5.
If a person reaches a square which is the base of a ladder, (s)he has to climb up that ladder, and he cannot come down on it. If a person reaches a square which has the mouth of the snake, (s)he has to go down the snake and come out through the tail - there is no way to climb down a ladder or to go up through a snake.

Input

The first line contains the number of tests, T. T testcases follow.

For each testcase, there are 3 lines.

The first line contains the number of ladders and snakes, separated by a comma.
The second is a list of comma separated pairs indicating the starting and ending squares of the ladders. The first point is the square from which a player can ascend and the second point is his final position.
The third is a list of comma separated pairs indicating the starting and ending (mouth and tail) squares of the snakes. the first point is the position of the mouth of the snake and the second one is the tail.
Multiple comma separated pairs of snakes and ladders are separated by a single space.


Output

Output description.

For each of the T test cases, output one integer, each of a new line, which is the least number of moves (or rolls of the die) in which the player can reach the target square (Square Number 100) after starting at the base (Square Number 1). This corresponds to the ideal sequence of faces which show up when the die is rolled.


Constraints

    1 ≤ T ≤ 10
    1 ≤ Number of snakes, Number of ladders ≤ 15


Example

Input:
3
3,7
32,62 42,68 12,98
95,13 97,25 93,37 79,27 75,19 49,47 67,17
5,8
32,62 44,66 22,58 34,60 2,90
85,7 63,31 87,13 75,11 89,33 57,5 71,15 55,25
4,9
8,52 6,80 26,42 2,72
51,19 39,11 37,29 81,3 59,5 79,23 53,7 43,33 77,21

Output:
3
3
5


Solution:

/*
    Assumptions: 
        There always exists a solution - ie.. the graph formed is always connected.
        There is no chain of snakes and ladders.

*/

#include<stdio.h>
#include<vector>
#include<map>
using namespace std;
struct Ladder_Snake
{
    int start,end;
};
class Vertex
{
    public:
    int distance,parent;
    bool isVisited;
    vector<int>adj_list;
    Vertex(){}
    Vertex(int distance,bool isVisited)
    {
        this->distance=distance;
        this->isVisited=isVisited;
    }
};
map<int , Vertex>graph;    // making the graph global
void bfs(int start)
{
    vector<int>q;
    q.push_back(start);
    
    graph[start].isVisited=true;
    graph[start].distance=0;
    graph[start].parent=0;
    
    while(q.size()!=0)
    {
        int v=q[0];
        q.erase(q.begin());
        for(int i=0;i<graph[v].adj_list.size();i++)
        {
            int u=graph[v].adj_list[i];
            if(graph[u].isVisited==false)
            {
                q.push_back(u);
                graph[u].parent=v;
                graph[u].isVisited=true;
                graph[u].distance=graph[v].distance+1;
            }
        }
    }
}

int isStart(int x,struct Ladder_Snake *arr,int n)
{
    for(int i=0;i<n;i++)
        if(arr[i].start==x)
            return arr[i].end;
    return -1;
}
void getNumbers(char*str,int *a,int *b)
{
    int flag=0,start=0,end=0;
    for(int j=0;str[j];j++)
    {
        if(str[j]==',')
            flag=1;continue;
        if(flag==0)
            start=start*10+str[j]-'0';
        else
            end=end*10+str[j]-'0';
    }
    (*a)=start;
    (*b)=end;    
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int ladders,snakes;
        char str[100];
        scanf("%s",str);
        getNumbers(str,&ladders,&snakes);
        
        struct Ladder_Snake ladder[15];
        for(int i=0;i<ladders;i++)
        {
            scanf(" %s",str);
            getNumbers(str,&(ladder[i].start),&(ladder[i].end));
        }
        
        struct Ladder_Snake snake[15];
        for(int i=0;i<snakes;i++)
        {
            scanf("%s",str);
            getNumbers(str,&(snake[i].start),&(snake[i].end));
        }
                
        for(int i=1;i<=100;i++)
        {
            if(isStart(i,snake,snakes)!=-1 || isStart(i,ladder,ladders)!=-1)
                continue;
            graph[i]=Vertex(0,false);
            for(int j=i+1;j<=100 && j<i+7;j++)
            {
                int x,y;
                x=isStart(j,snake,snakes);
                y=isStart(j,ladder,ladders);
                if(x!=-1)
                    graph[i].adj_list.push_back(x);
                else if(y!=-1)
                    graph[i].adj_list.push_back(y);
                else graph[i].adj_list.push_back(j);
            }
        }
        // graph construction completed here.
        // printing the graph.
        bfs(1);
        /*
        for(map<int,Vertex> ::iterator it=graph.begin();it!=graph.end();it++)
        {
            printf("%d -> ",it->first);
            Vertex v=it->second;
            for(int j=0;j<v.adj_list.size();j++)
            {
                printf("%d ",v.adj_list[j]);
            }
            printf("\t\t%d",v.parent);
            printf("\n");
        }
        */
        
        printf("%d\n",graph[100].distance);
        
    }
    return 0;
}

Chinese Remainder Theorem - Program in C

#include<stdio.h>
#include<stdlib.h>
long long int modularMultiplicativeInverse_BruteForce(long long int e,long long int mod)
{
    long long int i;
    for(i=1;i<mod;i++)
        if((e*i)%mod==1)
            return i;
}
int main()
{
    long long int i,n,*a,*b,*m,M,*Marray,answer;
    printf("Enter the number of Equations : \n");
    scanf("%lld",&n);
    a=(long long int*)malloc(sizeof(long long int)*n);
    m=(long long int*)malloc(sizeof(long long int)*n);
    Marray=(long long int*)malloc(sizeof(long long int)*n);
    printf("Enter the array a :\n");
    for(i=0;i<n;i++)
        scanf("%lld",&a[i]);
    printf("Enter the array m (all the elements of m should be pairwise co-prime) :\n");
    for(i=0;i<n;i++)
        scanf("%lld",&m[i]);
    M=1;
    for(i=0;i<n;i++)
        M*=m[i];
    for(i=0;i<n;i++)
        Marray[i]=M/m[i];
    answer=0;
    for(i=0;i<n;i++)
        answer = (answer + ((a[i] * Marray[i])%M * modularMultiplicativeInverse_BruteForce(Marray[i],m[i]))%M)%M;
    printf("x = %lld\n",answer);
    return 0;
}

Euclidean Algorithm for finding GCD of two numbers - Program in C

#include<stdio.h>

long long int gcd_Euclid_Recursive(long long int a,long long int b)
{
    if(b==0)
        return a;
    return gcd_Euclid_Recursive(b,a%b);
}


long long int gcd_Euclid_NonRecursive(long long int a,long long int b)
{
    long long int r;
    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}

int main()
{
    long long int a,b;
    printf("Enter two number : ");
    scanf("%lld%lld",&a,&b);
    printf("gcd(%lld,%lld) = %lld\n",a,b,gcd_Euclid_Recursive(a,b));
    printf("gcd(%lld,%lld) = %lld\n",a,b,gcd_Euclid_NonRecursive(a,b));
    return 0;
}

Rail Fence Cipher - Program in C

In the rail fence cipher, the plaintext is written downwards and diagonally on successive "rails" of an imaginary fence, then moving up when we reach the bottom rail. When we reach the top rail, the message is written downwards again until the whole plaintext is written out. The message is then read off in rows. For example, if we have 3 "rails" and a message of 'WE ARE DISCOVERED. FLEE AT ONCE', the cipherer writes out:

W . . . E . . . C . . . R . . . L . . . T . . . E
. E . R . D . S . O . E . E . F . E . A . O . C .
. . A . . . I . . . V . . . D . . . E . . . N . .

Then reads off to get the ciphertext:

WECRL TEERD SOEEF EAOCA IVDEN

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char *plainTextToCipherText(char plainText[],int n)
{
    int i,j,counter,limit,index=0,len;
    char *cipherText;
    len=strlen(plainText);
    cipherText=(char*)malloc(sizeof(char)*(len+1));
    for(i=0;i<n;i++)
 {
  counter=0;
  for(j=i;j<len;j+=limit)
  {
   cipherText[index++]=plainText[j];
   if(i==0 || i==n-1)
       limit=2*n-2;
   else if(counter%2==0)
    limit=2*(n-i-1);
   else
    limit=2*i;
   if(limit<=0)
       break;
   counter++;
  }
 }
 cipherText[index]='\0';
 return cipherText;
}
int main()
{
 int n;
 char plainText[100];
 printf("Enter the plain text : ");
 scanf("%s",plainText);
 printf("Enter the value of n : ");
 scanf("%d",&n);
    printf("%s\n",plainTextToCipherText(plainText,n)); 
 return 0;
}

RSA Algorithm - Program in C

RSA is one of the first practical public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, theencryption key is public and differs from the decryption key which is kept secret. In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem. RSA is made of the initial letters of the surnames ofRon Rivest, Adi Shamir and Leonard Adleman, who first publicly described the algorithm in 1977. 

The RSA algorithm involves three steps: key generation, encryption and decryption.

Key generation

RSA involves a public key and a private key. The public key can be known by everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted in a reasonable amount of time using the private key. The keys for the RSA algorithm are generated the following way:

1. Choose two distinct prime numbers p and q.
   • For security purposes, the integers p and q should be chosen at random, and should be of similar bit-length. Prime integers can be efficiently found using a primality test.
2. Compute n = pq.
   • n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.
3. Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1), where φ is Euler's totient function. This value is kept private.
4. Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e., e and φ(n) are coprime.
   • e is released as the public key exponent.
   • e having a short bit-length and small Hamming weight results in more efficient encryption – most commonly 2¹⁶ + 1 = 65,537. However, much smaller values of e (such as 3) have been shown to be less secure in some settings.^[5]
5. Determine d as d ≡ e⁻¹ (mod φ(n)); i.e., d is the modular multiplicative inverse of e (modulo φ(n)).

• This is more clearly stated as: solve for d given d⋅e ≡ 1 (mod φ(n))
• This is often computed using the extended Euclidean algorithm. Using the pseudocode in the Modular integers section, inputs a and n correspond to e and φ(n), respectively.
• d is kept as the private key exponent.

The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d, which must be kept secret. p, q, and φ(n) must also be kept secret because they can be used to calculate d.

Encryption

Alice transmits her public key (n, e) to Bob and keeps the private key d secret. Bob then wishes to send message M to Alice.

He first turns M into an integer m, such that 0 ≤ m < n by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext c corresponding to

This can be done efficiently, even for 500-bit numbers, using Modular exponentiation. Bob then transmits c to Alice.

Note that at least nine values of m will yield a ciphertext c equal to m,^{[note 1]}

Decryption[edit]

Alice can recover m from c by using her private key exponent d via computing

Given m, she can recover the original message M by reversing the padding scheme.

(In practice, there are more efficient methods of calculating c^d using the precomputed values below.)

A worked example[edit]

Here is an example of RSA encryption and decryption. The parameters used here are artificially small, but one can also use OpenSSL to generate and examine a real keypair.

1. Choose two distinct prime numbers, such as

    and 

2. Compute n = pq giving

   

3. Compute the totient of the product as φ(n) = (p − 1)(q − 1) giving

   

4. Choose any number 1 < e < 3120 that is coprime to 3120. Choosing a prime number for e leaves us only to check that e is not a divisor of 3120.

   Let 

5. Compute d, the modular multiplicative inverse of e (mod φ(n)) yielding,

   

   Worked example for the modular multiplicative inverse:

   

   

The public key is (n = 3233, e = 17). For a padded plaintext message m, the encryption function is

The private key is (d = 2753). For an encrypted ciphertext c, the decryption function is

For instance, in order to encrypt m = 65, we calculate

To decrypt c = 2790, we calculate

Both of these calculations can be computed efficiently using the square-and-multiply algorithm for modular exponentiation. In real-life situations the primes selected would be much larger; in our example it would be trivial to factor n, 3233 (obtained from the freely available public key) back to the primes p and q. Given e, also from the public key, we could then compute d and so acquire the private key.

/*
    Sample test case 1 :
        Choose p = 3 and q = 11
        Compute n = p * q = 3 * 11 = 33
        Compute φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20
        Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 7
        Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 3 [(3 * 7) % 20 = 1]
        Public key is (e, n) => (7, 33)
        Private key is (d, n) => (3, 33)
        The encryption of m = 2 is c = 27 % 33 = 29
        The decryption of c = 29 is m = 293 % 33 = 2
        
    Sample test case 2 :
        Choose p = 61 and q = 53
        Compute n = p * q = 61 * 53 = 3233
        Compute φ(n) = (p - 1) * (q - 1) = 60 * 52 = 3120
        Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 17
        Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 2753 [(2753 * 17) % 20 = 1]
        Public key is (e, n) => (17, 3233)
        Private key is (d, n) => (2753, 3233)
        The encryption of m = 65 is c = 2790
        The decryption of c = 2790 is m = 65
*/
#include<stdio.h>
/*
    Exponentiation by squaring
        http://en.wikipedia.org/wiki/Exponentiation_by_squaring
*/
long long int power(long long int a,long long int b,long long int mod)
{
    long long int t;
    if(b==0)
        return 1;
    else if(b==1)
        return a;
    t=power(a,b/2,mod);
    if(b%2==0)
        return (t*t)%mod;
    else
        return (((t*t)%mod)*a)%mod;
}

/*
    Euler's theorem may be used to compute modular inverse:
    According to Euler's theorem, if a is coprime to m, that is, gcd(a, m) = 1, then
        
        inverse of a = power(a,m-2) % m 
        
    but for Euler's m must be prime.
        and our mod will never be prime.
            because mod is phi(n) = (p-1)*(q-1) ... so this is never prime.
    so we cant apply Eulers Theorem to find multiplicative inverse of e
*/
/*
long long int modularMultiplicativeInverse_Euler(long long int e,long long int mod)
{
    return power(e,mod-2,mod);
}
*/
/*
long long int modularMultiplicativeInverse_ExtendedEuclideantheorem(long long int e,long long int mod)
{
    
}
*/
long long int modularMultiplicativeInverse_BruteForce(long long int e,long long int mod)
{
    long long int i;
    for(i=1;i<mod;i++)
        if((e*i)%mod==1)
            return i;
}
long long int encrypt(long long int m,long long int e,long long int n)
{
    return power(m,e,n);
}
long long int decrypt(long long int c,long long int d,long long int n)
{
    return power(c,d,n);
}
int main()
{
 long long int p,q,n,phin,d,e,m,c;
 // p and q should be prime numbers of similar bit length.
 printf("Enter the value of p and q (p and q should be primes of similar bit length) :\n");
 scanf("%lld%lld",&p,&q);
 n=p*q;
 phin=(p-1)*(q-1);

 printf("Enter an integer e such that 1 < e < %lld, and gcd(e,%lld)=1 : ",phin,phin);
 scanf("%lld",&e);

 printf("NOTE : %lld,%lld is your public key.\n",e,n);
 // e is called the public key exponent
 
 d=modularMultiplicativeInverse_BruteForce(e,phin);
 printf("NOTE : %lld,%lld is your private key.\n",d,n);
 // d is called the private key exponent
    
    printf("\nEnter the number to be encrypted : ");
    scanf("%lld",&m);
    c=encrypt(m,e,n); // sending the message to be encrypted and the public key.
    printf("the encrypted message is : %lld\n",c);
    
    printf("\nEnter the number to be decrypted : ");
    scanf("%lld",&c);
    m=decrypt(c,d,n); // sending the cipher message to be decrypted and the private key.
    printf("the decrypted message is : %lld\n",m);
 return 0;
}

Diffie Hellman Key Exchange Algorithm - Program in C

Diffie–Hellman establishes a shared secret that can be used for secret communications while exchanging data over a public network. The crucial part of the process is that Alice and Bob exchange their secret colors in a mix only. Finally this generates an identical key that is computationally difficult (impossible for modern supercomputers to do in a reasonable amount of time) to reverse for another party that might have been listening in on them. Alice and Bob now use this common secret to encrypt and decrypt their sent and received data. 

The simplest and the original implementation of the protocol uses the multiplicative group of integers modulo p, where p is prime, and g is a primitive root modulo p. Here is an example of the protocol, with non-secret values in blue, and secret values in red.

1. Alice and Bob agree to use a prime number p = 23 and base g = 5 (which is a primitive root modulo 23).
2. Alice chooses a secret integer a = 6, then sends Bob A = g^a mod p
   • A = 5⁶ mod 23 = 8
3. Bob chooses a secret integer b = 15, then sends Alice B = g^b mod p
   • B = 5¹⁵ mod 23 = 19
4. Alice computes s = B^a mod p
   • s = 19⁶ mod 23 = 2
5. Bob computes s = A^b mod p
   • s = 8¹⁵ mod 23 = 2
6. Alice and Bob now share a secret (the number 2).

/*
 this program calculates the Key
 for two persons
 using the Diffie Hellman Key exchange algorithm
*/
#include<stdio.h>
long long int power(int a,int b,int mod)
{
 long long int t;
 if(b==1)
  return a;
 t=power(a,b/2,mod);
 if(b%2==0)
  return (t*t)%mod;
 else
  return (((t*t)%mod)*a)%mod;
}
long long int calculateKey(int a,int x,int n)
{
 return power(a,x,n);
}
int main()
{
 int n,g,x,a,y,b;
 // both the persons will be agreed upon the common n and g
 printf("Enter the value of n and g : ");
 scanf("%d%d",&n,&g);

 // first person will choose the x
 printf("Enter the value of x for the first person : ");
 scanf("%d",&x);
 a=power(g,x,n);

 // second person will choose the y
 printf("Enter the value of y for the second person : ");
 scanf("%d",&y);
 b=power(g,y,n);

 printf("key for the first person is : %lld\n",power(b,x,n));
 printf("key for the second person is : %lld\n",power(a,y,n));
 return 0;
}

Reversing a Linked List using Recursion

#include<stdio.h>
#include<stdlib.h>

struct Node
{
	int data;
	struct Node*next;
};
struct Node*head;
struct Node*makeNode(int data)
{
	struct Node*node;
	node=(struct Node*)malloc(sizeof(struct Node));
	node->data=data;
	node->next=NULL;
	return node;
}
struct Node*insert(struct Node*start,struct Node*newNode)
{
	struct Node*ptr;
	if(start==NULL)
		return newNode;
	for(ptr=start;ptr->next;ptr=ptr->next);
	ptr->next=newNode;
	return start;
}
void printList(struct Node*start)
{
	struct Node*ptr;
	for(ptr=start;ptr;ptr=ptr->next)
		printf("%d ",ptr->data);
	printf("\n");
}
struct Node* reverseWithReturn(struct Node*node)
{
	struct Node*temp;
	if(node==NULL)
		return NULL;
	if(node->next==NULL)
		return node;
	temp=reverseWithReturn(node->next);
	node->next->next=node;
	node->next=NULL;
	return temp;
}
void reverseWithoutReturn(struct Node*node)
{
	/**
		for this function we need to maintain a global head
		this global head will be the head of new reversed list.

		this function will update the variable head
		now the head variable will store the start of newly formed list.
	*/
	if(node==NULL)
		return;
	if(node->next==NULL)
	{
		head=node;
		return ;
	}
	reverseWithoutReturn(node->next);
	node->next->next=node;
	node->next=NULL;
}
void reversePrint(struct Node*node)
{
	if(node==NULL)
		return;
	reversePrint(node->next);
	printf("%d ",node->data);
}
int main()
{
	struct Node*start;
	start=NULL;
	start=insert(start,makeNode(5));
	start=insert(start,makeNode(6));
	start=insert(start,makeNode(5));
	start=insert(start,makeNode(3));
	start=insert(start,makeNode(51));
	start=insert(start,makeNode(9));
	start=insert(start,makeNode(78));

	printList(start);
	start=reverseWithReturn(start);
	printList(start);

	return 0;
}

Hill Cipher - Program in C

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int **matrixMultiply(int**a,int r1,int c1,int **b,int r2,int c2)
{
 int **resultMatrix;
 int i,j,k,r,c;
 r=r1;c=c2;
 resultMatrix=(int**)malloc(sizeof(int*)*r);
 for(i=0;i<r;i++)
  resultMatrix[i]=(int*)malloc(sizeof(int)*c);
 for(i=0;i<r;i++)
 {
  for(j=0;j<c;j++)
  {
   resultMatrix[i][j]=0;
   for(k=0;k<c1;k++)
    resultMatrix[i][j]+=a[i][k]*b[k][j];
  }
 }
 return resultMatrix;
}
void printMatrix(int**matrix,int r,int c)
{
 int i,j;
 for(i=0;i<r;i++)
 {
  for(j=0;j<c;j++)
   printf("%d ",matrix[i][j]);
  printf("\n");
 }
}
int plainTextToCipherText(char plainText[],int**matrix)
{
 int len,**plainTextMatrix,**resultMatrix,i,j;
 // The matrix will be of dimensions strlen(plainText) by strlen(plainText)
 char *cipherText;
 len=strlen(plainText);
 cipherText=(char*)malloc(sizeof(char)*1000);

 // plainTextMatrix should be of dimension strlen(plainText) by 1
 // allcating memory to plainTextMatrix
 plainTextMatrix=(int**)malloc(sizeof(int*)*len);
 for(i=0;i<len;i++)
  plainTextMatrix[i]=(int*)malloc(sizeof(int)*1);

 // populating the plainTextMatrix
 for(i=0;i<len;i++)
  for(j=0;j<1;j++)
   plainTextMatrix[i][j]=plainText[i]-'a';

 resultMatrix=matrixMultiply(matrix,len,len,plainTextMatrix,len,1);
 
 // taking mod 26 of each element of the result matrix
 for(i=0;i<len;i++)
  for(j=0;j<1;j++)
   resultMatrix[i][j]%=26;

 // Printing the cipher text
 printf("The cipher text is as follows : ");
 for(i=0;i<len;i++)
  for(j=0;j<1;j++)
   printf("%c",resultMatrix[i][j]+'a');
 printf("\n");
 //printMatrix(resultMatrix,len,1);
}
int main()
{
 int len,i,j,**matrix;
 char plainText[1000];
 printf("Enter the word to be encrypted : ");
 scanf(" %s",plainText);
 len=strlen(plainText);

 // allocating memory to matrix
 matrix=(int**)malloc(sizeof(int*)*len);
 for(i=0;i<len;i++)
  matrix[i]=(int*)malloc(sizeof(int)*len);

 printf("Enter the matrix of %d by %d to be used in encryption process : \n",len,len);
 for(i=0;i<len;i++)
  for(j=0;j<len;j++)
   scanf("%d",&matrix[i][j]);

 plainTextToCipherText(plainText,matrix);
 return 0;
}

Caesar Cipher - Program in C

#include<stdio.h>
#include<stdlib.h>
char*plainTextToCipherText(char plainText[],int n)
{
 char *cipherText;
 int i;
 cipherText=(char*)malloc(sizeof(char)*1000);
 for(i=0;plainText[i];i++)
 {
  if(plainText[i]!=' ')
   cipherText[i]=((plainText[i]-'a'+n)%26)+'a';
  else
   cipherText[i]=plainText[i];
 }
 cipherText[i]='\0';
 return cipherText;
}
char*cipherTextToPlainText(char cipherText[],int n)
{
 char *plainText,c;
 int i;
 plainText=(char*)malloc(sizeof(char)*1000);
 for(i=0;cipherText[i];i++)
 {
  if(cipherText[i]!=' ')
  {
   c=(cipherText[i]-'a'-n)%26;
   if(c<0)
    c+=26;
   c+='a';
   plainText[i]=c;
  }
  else
  {
   plainText[i]=cipherText[i];
  }
 }
 plainText[i]='\0';
 return plainText;
}
int main()
{
 int n;
 char plainText1[1000],*cipherText1,cipherText2[1000],*plainText2;

 // Encoding Cipher Text
 printf("Enter the Plain Text (in lower case): ");
 scanf(" %[^\n]s",plainText1);
 printf("Enter the number of characters to be shifted : ");
 scanf("%d",&n);
 cipherText1=plainTextToCipherText(plainText1,n);
 printf("Cipher Text is : %s\n",cipherText1);


 // Decoding Plain Text
 printf("\nEnter the Cipher Text (in lower case) : ");
 scanf(" %[^\n]s",cipherText2);
 printf("Enter the number of charaters to be shifted : ");
 scanf("%d",&n);
 plainText2=cipherTextToPlainText(cipherText2,n);
 printf("The Plain Text is : %s\n",plainText2);
 return 0;
}

Generic Representation of Graph - Generic List of Vertices and Edges

LinkedList_Generic.h

struct LinkedList_Generic
{
 struct ListNode_Generic*start;
 int elementSize;
 /*
  elementSize, will store the size of each element. 
  The element size is important, because generics in C are limited to void pointers, 
  in order to let the compiler know the amount of memory needed by malloc/memcpy. 
  This information should always be supplied dynamically. The caller should use sizeof(int) rather than 4.
 */
};
struct ListNode_Generic
{
 void *data;
 struct ListNode_Generic*next;
};
struct LinkedList_Generic *makeAndInitialiseLinkedList();
struct ListNode_Generic *makeAndInitialiseListNode(struct LinkedList_Generic *list,void*element);
void addElement(struct LinkedList_Generic*list,struct ListNode_Generic*element);
void removeElement(struct LinkedList_Generic*list,struct ListNode_Generic*node);
struct ListNode_Generic*getNodeReferenceWithGivenData(struct LinkedList_Generic*list,void*data);

LinkedList_Generic.c

#include<stdlib.h>
#include<string.h>
#include"LinkedList_Generic.h"

struct LinkedList_Generic *makeAndInitialiseLinkedList(int elementSize)
{
 struct LinkedList_Generic *list;
 list=(struct LinkedList_Generic*)malloc(sizeof(struct LinkedList_Generic));
 list->start=NULL;
 list->elementSize=elementSize;
 return list;
}
struct ListNode_Generic *makeAndInitialiseListNode(struct LinkedList_Generic *list,void*element)
{
 struct ListNode_Generic*listNode;
 listNode=(struct ListNode_Generic*)malloc(sizeof(struct ListNode_Generic));
 listNode->data=element;
 //listNode->data=malloc(sizeof(list->elementSize));
 //memcpy(listNode->data,element,list->elementSize);
 listNode->next=NULL;
 return listNode;
}
void addElement(struct LinkedList_Generic*list,struct ListNode_Generic*element)
{
 struct ListNode_Generic*ptr,*prev;
 if((list->start)==NULL)
  (list->start)=element;
 else
 {
  for(ptr=(list->start);ptr;prev=ptr,ptr=ptr->next);
  (prev->next)=element;
 }
}
void removeElement(struct LinkedList_Generic*list,struct ListNode_Generic*node)
{
 struct ListNode_Generic*ptr,*prev;
 for(ptr=(list->start),prev=NULL;ptr && (ptr)!=node;prev=ptr,ptr=ptr->next);
 if(ptr)
 {
  if(prev!=NULL)
  {
   prev->next=ptr->next;
   if(ptr)
   {
    free(ptr);
   }
  }
  else if(prev==NULL && ptr!=NULL) // means the element that we need to delete is the start of the list.
  {
   prev=list->start;
   (list->start)=((list->start)->next);
   if(prev)
   {
    free(prev);
   }
  }
 }
}
struct ListNode_Generic*getNodeReferenceWithGivenData(struct LinkedList_Generic*list,void*data)
{
 struct ListNode_Generic*node;
 for(node=list->start;node;node=node->next)
 {
  if((node->data)==data)
   return node;
 }
}

Graph_Generic.h

struct Graph_Generic
{
 struct LinkedList_Generic *vertexList,*edgeList;
 int numberOfVertices, numberOfEdges;
};
struct Vertex
{
 int id;
 int inDegree,outDegree;
};
struct Edge
{
 int id,sourceVertex,destinationVertex,isDirected,weight;
};
struct Graph_Generic*makeAndInitialiseGraph();
void addVertex(struct Graph_Generic*graph,struct Vertex*vertex);
void removeVertex(struct Graph_Generic*graph,int vertexNumber);
void addEdge(struct Graph_Generic*graph,struct Edge*edge);
void removeEdge(struct Graph_Generic *graph,int ,int ,int);
struct Edge *makeEdge(int sourceVertex,int destinationVertex,int weight,int isDirected);
struct Vertex *makeVertex();
void printGraph_Generic(struct Graph_Generic*grpah);

Graph_Generic.c

#include"Graph_Generic.h"
#include"LinkedList_Generic.h"
#include<stdlib.h>
#include<stdio.h>
struct Graph_Generic*makeAndInitialiseGraph()
{
 struct Graph_Generic*graph;
 graph=(struct Graph_Generic*)malloc(sizeof(struct Graph_Generic));
 graph->numberOfVertices=0;
 graph->numberOfEdges=0;
 graph->vertexList=makeAndInitialiseLinkedList(sizeof(struct Vertex));
 graph->edgeList=makeAndInitialiseLinkedList(sizeof(struct Edge));
 return graph;
}
struct Edge *makeEdge(int sourceVertex,int destinationVertex,int weight,int isDirected)
{
 static int edgeNumber=0;
 struct Edge*edge;
 edge=(struct Edge*)malloc(sizeof(struct Edge));
 edge->sourceVertex=sourceVertex;
 edge->destinationVertex=destinationVertex; 
 edge->weight=weight;
 edge->isDirected=isDirected;
 edge->id=edgeNumber++;
 return edge;
}
struct Vertex *makeVertex()
{
 static int vertexNumber=0;
 struct Vertex*vertex;
 vertex=(struct Vertex*)malloc(sizeof(struct Vertex));
 (vertex->id)=vertexNumber++;
 return vertex;
}

void addVertex(struct Graph_Generic*graph,struct Vertex*vertex)
{
 (graph->numberOfVertices)++;
 addElement(graph->vertexList,makeAndInitialiseListNode(graph->vertexList,vertex));
}
void removeVertex(struct Graph_Generic*graph,int vertexNumber)
{
 struct Edge*e;
 struct ListNode_Generic*ptr,*ptr1;
 (graph->numberOfVertices)--;
 for(ptr=graph->vertexList->start;ptr;ptr=ptr->next)
 {
  if(((struct Vertex*)(ptr->data))->id==vertexNumber)
   break;
 }
 if(ptr)
 {
  /*
   when you will be deleting an vertex then all the edges from and to that vertex should be deleted.
  */
  for(ptr1=graph->edgeList->start;ptr1;ptr1=ptr1->next)
  {
   e=(struct Edge*)(ptr1->data);
   if(e->sourceVertex==vertexNumber || e->destinationVertex==vertexNumber)
    removeEdge(graph,e->sourceVertex,e->destinationVertex,e->weight);
  }
  removeElement(graph->vertexList,ptr);
 }
}
void addEdge(struct Graph_Generic*graph,struct Edge*edge)
{
 (graph->numberOfEdges)++;
 addElement(graph->edgeList,makeAndInitialiseListNode(graph->edgeList,edge));
}
void removeEdge(struct Graph_Generic *graph,int sourceVertex,int destinationVertex,int weight)
{
 struct ListNode_Generic*ptr;
 (graph->numberOfEdges)--;
 for(ptr=(graph->edgeList->start);ptr;ptr=ptr->next)
 {
  if(
   ((struct Edge*)(ptr->data))->sourceVertex==sourceVertex &&
   ((struct Edge*)(ptr->data))->destinationVertex==destinationVertex &&
   ((struct Edge*)(ptr->data))->weight==weight
  ) break;
 }
 if(ptr)
  removeElement(graph->edgeList,ptr);
}
void printGraph_Generic(struct Graph_Generic*graph)
{
 int i;
 struct ListNode_Generic*ptr;
 printf("\nPrinting the vertex List : \n");
 printf("\nTotal Number Of Vertices in the Graph : %d\n",graph->numberOfVertices);
 for(ptr=(struct ListNode_Generic*)((graph->vertexList)->start);ptr;ptr=ptr->next)
  printf("%d ",((struct Vertex*)(ptr->data))->id);
 printf("\nTotal Number Of Edges in the Graph : %d\n",graph->numberOfEdges);
 for(ptr=(struct ListNode_Generic*)((graph->edgeList)->start);ptr;ptr=ptr->next)
  printf("Edge No. : %d, from %d to %d with weight=%d and isDirected?=%d\n",((struct Edge*)(ptr->data))->id,((struct Edge*)(ptr->data))->sourceVertex,((struct Edge*)(ptr->data))->destinationVertex,((struct Edge*)(ptr->data))->weight,((struct Edge*)(ptr->data))->isDirected);
}

main.c

#include<stdio.h>
#include"Graph_Generic.h"
int main()
{
 struct Graph_Generic*graph;
 int a,b,weight,isDirected,i,numberOfVertices,numberOfEdges,sourceVertex,destinationVertex,vertexNumber;

 printf("Enter the number of Vertices in the Graph : ");
 scanf("%d",&(numberOfVertices));
 printf("Enter the number of Edges in the Graph : ");
 scanf("%d",&(numberOfEdges));

 graph=makeAndInitialiseGraph();

 for(i=0;i<numberOfVertices;i++)
  addVertex(graph,makeVertex());

 printf("NOTE 1 : The ordering of the Vertices and Edges is zero indexed.\n");
 printf("NOTE 2 : For each edge enter the following in Sequence : \n");
 printf("\t1. Source Vertex Number.\n");
 printf("\t2. Destination Vertex Number.\n");
 printf("\t3. Weight associated with Edge.\n");
 printf("\t4. 1 if the Edge is Directed, and 0 otherwise.\n");
 
 for(i=0;i<numberOfEdges;i++)
 {
  printf("Enter the edge Number %d : ",i+1);
  scanf("%d%d%d%d",&a,&b,&weight,&isDirected);
  addEdge(graph,makeEdge(a,b,weight,isDirected));
 }
 printGraph_Generic(graph);
 
 printf("\nDeleting an Edge : \n");
 printf("Enter the sourceVertex, destinationVertex and weight of the graph : ");
 scanf("%d%d%d",&sourceVertex,&destinationVertex,&weight);
 removeEdge(graph,sourceVertex,destinationVertex,weight);
 
 printf("Deleting a Vertex : \n");
 printf("Enter the Vertex number to be deleted : ");
 scanf("%d",&vertexNumber);
 removeVertex(graph,vertexNumber);
 
 printGraph_Generic(graph);
 
 printf("Program Execution Successful...\n");
 return 0;
}

Makefile

all: LinkedList_Generic.o Graph_Generic.o main.o
 gcc LinkedList_Generic.o Graph_Generic.o main.o -o hello
LinkedList_Generic.o: LinkedList_Generic.c
 gcc -c LinkedList_Generic.c
Graph_Generic.o: Graph_Generic.c
 gcc -c Graph_Generic.c
main.o: main.c
 gcc -c main.c
clean:
 rm -rf *.o *~ hello

SampleInputData.txt

6
9
1 0 1 1
1 3 1 1
1 2 1 1 
0 5 1 1
0 4 1 1
2 3 1 1
2 4 1 1
2 5 1 1
4 3 1 1
2 5 1
0

Adjacency Matrix Representation of Graph

one_D_bit_array.h

int get_one_D_bit_array(int ,int *);
void reset_one_D_bit_array(int ,int *);
void set_one_D_bit_array(int ,int *);

one_D_bit_array.c

#include"one_D_bit_array.h"
int get_one_D_bit_array(int i,int* arr)
{
 if((arr[i/32]&((unsigned int)1<<(31-i%32)))!=0)
  return 1;
 return 0;
}
void set_one_D_bit_array(int i,int *arr)
{
 arr[i/32]|=((unsigned int)1<<(31-i%32));  // to set its 31-(n%32) th bit.
}
void reset_one_D_bit_array(int i,int *arr)
{
 arr[i/32]&=(~((unsigned int)1<<(31-i%32))); // to reset its 31-(n%32) th bit.
}

two_D_bit_array.h

int get_two_D_bit_array(int ,int ,int *,int);
void set_two_D_bit_array(int ,int ,int *,int);
void reset_two_D_bit_array(int ,int ,int *,int);

two_D_bit_array.c

#include"two_D_bit_array.h"

/*  
  this function will return bit value in 
  ith row and 
  jth column
  from the array 'arr'
  which provides an abstraction of 2-D bit array of size n * n.
*/ 
int get_two_D_bit_array(int i,int j,int* arr,int n)
{
 int bitNumber=i*n+j;
 if((arr[bitNumber/32]&((unsigned int)1<<(31-bitNumber%32)))!=0)
  return 1;
 return 0;
}

/*  
  this function will set the bit value in 
  ith row and 
  jth column
  in the array 'arr'
  which provides an abstraction of 2-D bit array of size n * n
  to 1.
*/ 
void set_two_D_bit_array(int i,int j,int *arr,int n)
{ 
 int bitNumber=i*n+j;
 arr[bitNumber/32]|=((unsigned int)1<<(31-bitNumber%32));  // to set its 31-(bitNumber%32) th bit.
}

/*  
  this function will set the bit value in 
  ith row and 
  jth column
  in the array 'arr'
  which provides an abstraction of 2-D bit array of size n * n
  to 0.
*/ 
void reset_two_D_bit_array(int i,int j,int *arr,int n)
{
 int bitNumber=i*n+j;
 arr[bitNumber/32]&=(~((unsigned int)1<<(31-bitNumber%32))); // to reset its 31-(bitNumber%32) th bit.
}

Graph_AdjacencyMatrix.h

struct Graph
{
 int numberOfVertices,numberOfEdges;
 unsigned int*adjacencyMatrix;
};
struct Graph*makeNewGraph();
void initializeAdjacencyMatrix(struct Graph*);
void createEdge(struct Graph*,int,int);
void removeEdge(struct Graph*,int,int);
void showAdjacencyMatrix(struct Graph*);
int findNumberOfComponents(struct Graph*);

Graph_AdjacencyMatrix.c

#include<stdio.h>
#include<stdlib.h>
#include"Graph_AdjacencyMatrix.h"
#include"two_D_bit_array.h"
#include"one_D_bit_array.h"

struct Graph*makeNewGraph()
{
 struct Graph*g;
 g=(struct Graph*)malloc(sizeof(struct Graph));
 return g;
}
void initializeAdjacencyMatrix(struct Graph*g)
{
 /*
  The adjacencyMatrix corresponding to vertex u and v will contain 1 if there is an edge from u to v
  otherwise it will contain 0

  Description of data structure used for making adjacencyMatrix:
   * We will need n*n bits to represent the existence of an edge between two vertices
   * These n*n bits should be assumed to be arranged in the linear fashion
   * For implementing this linear fashion we will use an array of integers.
   * For a standard 32 bit compiler (like gcc 4.8.2) size of an integer is 32 bits (4 bytes).
   * By this linear arrangement of AdjacencyMatrix we will optimally exploit every single bit.
 */
 int sizeOfIntegerColumns,i,j;
 sizeOfIntegerColumns=((g->numberOfVertices)*(g->numberOfVertices))/32+1;
 (g->adjacencyMatrix)=(unsigned int*)malloc(sizeof(unsigned int)*sizeOfIntegerColumns);
 for(i=0;i<sizeOfIntegerColumns;i++)
  (g->adjacencyMatrix)[i]=0;
}
void createEdge(struct Graph*g,int a,int b)
{
 set_two_D_bit_array(a,b,g->adjacencyMatrix,g->numberOfVertices);
}
void removeEdge(struct Graph*g,int a,int b)
{
 reset_two_D_bit_array(a,b,g->adjacencyMatrix,g->numberOfVertices);
}
void showAdjacencyMatrix(struct Graph*g)
{
 int i,j,bitNumber;
 printf("The adjacency Matrix of the Graph is as follows : \n");
 for(i=0;i<(g->numberOfVertices);i++)
 {
  for(j=0;j<(g->numberOfVertices);j++)
   printf("%d",get_two_D_bit_array(i,j,g->adjacencyMatrix,g->numberOfVertices));
  printf("\n");
 }
}

int findNumberOfComponents(struct Graph*g)
{
 /*
  first of all we need to create a copy of the AdjacencyMatrix.
 */
 unsigned int *adjacencyMatrix_copy,*flag,sizeOfIntegerColumns,i,j,k,components;
 sizeOfIntegerColumns=((g->numberOfVertices)*(g->numberOfVertices))/32+1;
 adjacencyMatrix_copy=(unsigned int*)malloc(sizeof(unsigned int)*sizeOfIntegerColumns);
 for(i=0;i<sizeOfIntegerColumns;i++)
  adjacencyMatrix_copy[i]=(g->adjacencyMatrix)[i];
 /* copy of adjacencyMatrix created */

 /*  now we need to keep the track of vertices being merged
  for this we need to introduce a one-D bit array that will keep track of this information.
  let this one-D bit array be flag.
 */
 flag=(unsigned int *)malloc(sizeof(unsigned int)*(g->numberOfVertices)/32+1);
 for(i=0;i<(g->numberOfVertices)/32+1;i++)
  flag[i]=0;
 /*
  if the nth bit of flag array is 0 this means that the vertex with vertexNumber 'n' is still
  alive and is not merged with any other vertex.

  if the nth bit of flag array is 1 this means that the vertex with vertexNumber 'n' is dead
  and is merged with some other vertex and has no existence now.
 */
 /* now we are ready for merging vertices in our dummy (copied) adjacencyMatrix.  */
 for(i=0;i<(g->numberOfVertices);i++)
 {
  if(get_one_D_bit_array(i,flag)==0) // means ith vertex is alive
  {
   for(j=0;j<(g->numberOfVertices);j++)
   {
    if(j!=i && get_one_D_bit_array(j,flag)==0) // means the jth vertex is alive
    {
     if(get_two_D_bit_array(i,j,adjacencyMatrix_copy,g->numberOfVertices)==1)
     {
      /*
       now we need to merge the ith node with the jth node
       for this we need to merge
        ith row with jth row, and
        ith col with jth col
      */
      for(k=0;k<(g->numberOfVertices);k++) // merging the ith and jth rows
      {
       if(get_two_D_bit_array(i,k,adjacencyMatrix_copy,g->numberOfVertices) | get_two_D_bit_array(j,k,adjacencyMatrix_copy,g->numberOfVertices))
        set_two_D_bit_array(i,k,adjacencyMatrix_copy,g->numberOfVertices);
      }
      for(k=0;k<(g->numberOfVertices);k++) // merging the ith and jth cols
      {
       if(get_two_D_bit_array(k,i,adjacencyMatrix_copy,g->numberOfVertices) | get_two_D_bit_array(k,j,adjacencyMatrix_copy,g->numberOfVertices))
        set_two_D_bit_array(k,i,adjacencyMatrix_copy,g->numberOfVertices);
      }
      /* now the jth vertex is merged with ith vertex so the ith vertex should have no existence */
      /* so we need to set the jth bit of flag array to 1 */
      set_one_D_bit_array(j,flag); // declaring that the jth vertex is now dead.
     }
    }
   }
  }
 }
 /* 
  now the total number of components in the graph will be the number of vertices that still have zero 
  correponding to their vertex number in flag array.
 */
 components=0;
 for(i=0;i<(g->numberOfVertices);i++)
  if(get_one_D_bit_array(i,flag)==0)
   components++;
 return components;
}

main.c

#include<stdio.h>
#include"Graph_AdjacencyMatrix.h"

int main()
{
 int i,n,a,b;
 struct Graph*g;
 g=makeNewGraph();
 printf("Enter the number of Vertices in the Graph : ");
 scanf("%d",&(g->numberOfVertices));
 printf("Enter the number of Edges in the Graph : ");
 scanf("%d",&(g->numberOfEdges));
 initializeAdjacencyMatrix(g);
 printf("NOTE : The ordering of the vertices is zero indexed.\n");
 for(i=0;i<(g->numberOfEdges);i++)
 {
  printf("Enter the edge Number %d : ",i+1);
  scanf("%d%d",&a,&b);
  createEdge(g,a,b);
 }
 showAdjacencyMatrix(g);
 printf("Number of components in the Graph = %d\n",findNumberOfComponents(g));
 printf("\nProgram execution successful...\n");
 return 0;
}

Makefile

all: hello
hello: one_D_bit_array.o two_D_bit_array.o Graph_AdjacencyMatrix.o main.o
 gcc one_D_bit_array.o two_D_bit_array.o Graph_AdjacencyMatrix.o main.o -o hello
one_D_bit_array.o: one_D_bit_array.c
 gcc -c one_D_bit_array.c
two_D_bit_array.o: two_D_bit_array.c
 gcc -c two_D_bit_array.c
main.o: main.c
 gcc -c main.c
graph.o: Graph_AdjacencyMatrix.c
 gcc -c Graph_AdjacencyMatrix.c
clean:
 rm -rf *~ *.o hello

SampleTestData.txt

4
8
0 2
2 0
1 3
3 1
0 3
3 0
3 2
2 3