Strongly Connected Component (SCC)

Strongly Connected Components pseudocode:

SCC(G)

1. call DFS(G) to compute finishing times f [u] for all u
2. compute G^T
3. call DFS(G^T), but in the main loop, consider vertices in order of decreasing f [u] (as computed in first DFS)
4. output the vertices in each tree of the depth-first forest formed in second DFS as a separate SCC

Here is a simple implementation:

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define sz 100
vector<int> graph[sz],Gt[sz]; //graph[] store the graph and Gt[] store transpose graph
vector<int> topo;
int disc[sz],fin[sz],color[sz];
int time=0;

void dfs_visit(int node,int flag)
{
    int i,j,k,temp;

    color[node]=1;
    if(flag==0) //for the general graph, first dfs call
    {
        disc[node]= ++time;

        for(i=0;i<graph[node].size();i++)
        {
            temp=graph[node][i];
            if(color[temp]==0)
                dfs_visit(temp,flag);
        }
        fin[node]= ++time;
        topo.push_back(node);
    }
    else //for the transpose graph, second dfs call
    {
        printf("%d ",node);
        for(i=0;i<Gt[node].size();i++)
        {
            temp=Gt[node][i];
            if(color[temp]==0)
                dfs_visit(temp,flag);
        }
    }

    color[node]=2;
}


void dfs(int node,int flag)
{
    int i,j;

    if(flag==0) //for the general graph, first dfs call
    {
        for(i=0;i<node;i++)
        {
            if(color[i]==0)
                dfs_visit(i,flag);
        }
    }
    else //for the transpose graph, second dfs call
    {
        for(i=0;i<topo.size();i++)
        {
            if(color[topo[i]]==0)
            {
                dfs_visit(topo[i],flag);
                puts("");
            }

        }
    }
}

int main()
{
    int i,j,k,num,t,node,edge,a,b;

    scanf("%d%d",&node,&edge);

    for(i=0;i<edge;i++)
    {
        scanf("%d%d",&a,&b);
        graph[a].push_back(b);  //directed graph
        Gt[b].push_back(a);     //transpose graph
    }

 //dfs in graph
    for(i=0;i<node;i++) color[i]=0;
    
 dfs(node,0);
 
 //finding topological sort
    reverse(topo.begin(),topo.end());
    
    //dfs in transpose graph
    for(i=0;i<node;i++) color[i]=0;
 
    dfs(node,1); //connected components will be printed in this call

    return 0;
}

Topological Sort

Topological Sort pseudocode:

TOPOLOGICAL-SORT(V, E)

1. Call DFS(V, E) to compute finishing times f[v] for each vertex v
2. When each vertex is finished, insert it onto the front of a linked list
3. Return the linked list of vertices

The graph must be acyclic, Otherwise topological ordering is not possible.

Here is a simple implementatin of Topological Sort:

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define sz 100

vector<int> graph[sz]; //storing the graph
vector<int> topo; //storing the topo ordering
int disc[sz],fin[sz],color[sz];
int time=0;

void dfs_visit(int node)
{
    int i,j,k,temp;
    color[node]=1;
    disc[node]= ++time; //discovery time

    for(i=0;i<graph[node].size();i++)
    {

        temp=graph[node][i];
        if(color[temp]==0)
        {
            dfs_visit(temp);
        }
    }
    color[node]=2;
    fin[node]= ++time; //finishing time
    topo.push_back(node);
}


void dfs(int node)
{
    int i;

    for(i=0;i<node;i++)
    {
        if(color[i]==0)
        {
            dfs_visit(i);
        }
    }
}

int main()
{
    int i,j,k,num,t,node,edge,a,b;

    scanf("%d%d",&node,&edge); //number of node and edges

    for(i=0;i<edge;i++)
    {
        scanf("%d%d",&a,&b);
        graph[a].push_back(b); //directed graph
    }
 
 //initialization
    for(i=0;i<node;i++) color[i]=0;

    dfs(node); //calling dfs to calculate discovery and finishing time
 
 /*
    for(i=0;i<node;i++)
        printf("%d-> %d %d\n",i,disc[i],fin[i]);
 */
 
 //here i use stl vector, so i need to reverse the list
 //using stl list wouldn't need this line
    reverse(topo.begin(),topo.end()); 
 
    printf("Topological Sort:\n");
    for(i=0;i<topo.size();i++)
        printf("%d ",topo[i]);


    return 0;
}

Depth First Search

Depth First Search pseudocode:

DFS(G) 
{
 //initialize
 for each vertex u in V
 {
  color[u] = WHITE;
  prev[u]=NIL;
  f[u]=inf; d[u]=inf;
 }
 time = 0;
 for each vertex u in V
  if (color[u] == WHITE)
   DFS_Visit(u);
}

DFS_Visit(u)
{
 color[u] = GREY;
 time = time+1;
 d[u] = time;
 for each v in Adj[u]
 {
  if(color[v] == WHITE)
  {
   prev[v]=u;
   DFS_Visit(v);
  }
 }
 color[u] = BLACK;
 time = time+1;
 f[u] = time;
}

Breadth First Search (BFS)

Breadth First Search algorithm pseudocode:

//color[]= {white=not visited, gray=visiting-not finished, black=visited}
//prev[]= parent
//d[]= distance

BFS(G) 
{
 //initialization
 for each vertex u in V-{s}
 {
  color[u]=WHITE;
  prev[u]=NIL;
  d[u]=inf;
 }
        //initializing source
 color[s]=GRAY;
 d[s]=0; 
 prev[s]=NIL;
 Q=empty;
 ENQUEUE(Q,s);
 
 While(Q not empty)
 {
  u = DEQUEUE(Q);
  for each v in adj[u]{
  if (color[v] == WHITE)
  {
   color[v] = GREY;
   d[v] = d[u] + 1;
   prev[v] = u;
   Enqueue(Q, v);
  }
 }
 color[u] = BLACK;
 }
}

Path print:

Print-Path(G, s, v)

if v = s
        then print s
        else   if π[v] ← NIL
                then  print "no path exists from " s "to" v"
                else   Print-Path(G, s, π[v])
                        print v

Josephus Recurrence

Famous Josephus's problem solution.

Recursive solution:

int josephus(int n, int m)   
{   
 if (n == 1)  
      return 0;   
 return (josephus (n-1, m) + m) % n;   
}

Iterative solution:

ans=0;
for(i=2;i<=n;i++)
{
 ans=(ans+m)%i;
}

when m=2, then the following will be useful. Found it here.

int f(int n) 
{
    if(n == 1) return 1;
    return (f((n-(n&1))>>1)<<1) + ((n&1)?1:-1);
}

nCr using Dynamic programming

Here is a technique to calculate nCr using DP.

From pascal's triangular relation, we get,
nCr =( n-1)C(r) + (n-1)C(r-1)

The basic idea lies behind DP-
nCn = 1
nC1 = n
nC0 = 1
and
nCr = n-1Cr + n-1Cr-1

So the code forms like following-

#define i64 unsigned long long

i64 dp[66][33];

i64 nCr(int n, int r)
{
 if(n==r) return dp[n][r] = 1;
 if(r==0) return dp[n][r] = 1;
 if(r==1) return dp[n][r] = (i64)n;
 if(dp[n][r]) return dp[n][r];
 return dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1);
}

Binary Search

//array must be sorted

bool b_search(int arr[],int strt,int lst,int target) //strt=starting index, lst=last index
{
    int lo=strt,hi=lst;

    while(lo<=hi)
    {
        int mid=lo+(hi-lo)/2;

        if(arr[mid]==target)
            return true;
        else if(arr[mid]<target)
            lo=mid+1;
        else
            hi=mid-1;
    }

    return false;
}

Counting sort

This function use counting sort.

To work with it send parameter as (array_name,size_of_array,number_range). where number range is the highest possible value in the given data array.

void counting_sort(int arr[], int sz,int range)
{
    int i,j;
    int tmp[100];

    memset(tmp,0,sizeof(tmp));

    for(i=0;i<sz;i++)
        tmp[arr[i]]++;

    for(i=0,j=0;i<range;i++)
    {
        while(tmp[i]>0)
        {
            arr[j++]=i;
            tmp[i]--;
        }
    }
}

This code will only work for numbers>1. To include 0 or negative number, the function can be slightly modified. 

Merge sort

To calculate Merge sort call the Merge_Sort function with (array, starting_index, ending_index).

void Merge(int A[], int p, int q, int r)
{
    int i, j, k, n1 = q - p + 1, n2 = r - q;
//n1=number of element at left, n2=number of element at right
    int L[n1], R[n2];

    for(i = 0; i < n1; i++)
        L[i] = A[p + i];

    for(j = 0; j < n2; j++)
        R[j] = A[q + j + 1];

    for(k = p, i = j = 0; k <= r; k++) {
        if(j >= n2 || (i < n1 && L[i] <= R[j]))
        {
            A[k] = L[i++];
        }
        else
        {
            A[k] = R[j++];
        }
    }
}

void Merge_Sort(int A[], int p, int r)
{
    if(p < r) {
        int q = (p + r) / 2;
        Merge_Sort(A, p, q);
        Merge_Sort(A, q+1, r);
        Merge(A, p, q, r);
    }
}

Selection sort

Selection sort function-

void selection_sort(int arr[], int n)
{
	int j,temp,ipos,imin;

	for(ipos=0;ipos<n-1;ipos++)
	{
		imin=ipos;
		for(j=ipos+1;j<n;j++)
		{
			if(arr[imin]>arr[j])
				imin=j;
		}
		if(ipos!=imin)
		{
			temp=arr[ipos];
			arr[ipos]=arr[imin];
			arr[imin]=temp;
		}
	}
}

Insertion sort

Insertion sort function-

void insertion_sort(int arr[], int n)
{
    int i,j,value;

    for(i=1;i<n;i++)
    {
        value=arr[i];
        for(j=i-1;j>=0 && arr[j]>value;j--)
        {
            arr[j+1]=arr[j];
        }
        arr[j+1]=value;
    }
}

Bubble Sort

Bubble sort function-

void bubble_sort(int arr[], int n)
{
	int i,j,temp;

	for(i=n-1;i>=0;i--)
	{
		for(j=1;j<=i;j++)
		{
			if(arr[j-1]>arr[j])
			{
				temp=arr[j-1];
				arr[j-1]=arr[j];
				arr[j]=temp;
			}
		}
	}
}

Extended euclid algorithm

While the euclidean algorithm simply finds the greatest common divisor of two numbers a and b, The extended euclidean algorithm finds the GCD also factors in addition to x and y such that:

That is, it finds the coefficients by which the GCD of two numbers expressed in terms of the numbers themselves.
Details can be found here and here.

Implementation of extended euclidean algorithm-

int gcd ( int a, int b, int & x, int & y ) {
	if ( a == 0 ) {
		x = 0 ; y = 1 ;
		return b ;
	}
	int x1, y1 ;
	int d = gcd ( b % a, a, x1, y1 ) ;
	x = y1 - ( b / a ) * x1 ;
	y = x1 ;
	return d ;
} 

This is a recursive function, which still returns the GCD of the numbers a and b, But apart from that- the value of x and y passed as reference to the function.

Here is another c++ implementation which uses class to handle the value of x,y and d.  I found it here.

class Euclid {
public:
    i64 x, y, d;
    Euclid() {}
    Euclid(i64 _x, i64 _y, i64 _d) : x(_x), y(_y), d(_d) {}
};
 
Euclid egcd(i64 a, i64 b) {
    if(!b) return Euclid(1, 0, a);
    Euclid r = egcd(b, a % b);
    return Euclid(r.y, r.x - a / b * r.y, r.d);
}

Big Mod

Big Mod algorithm simply use the modular arithmetic to find the value of-

(a^p)%m.

Big Mod recursive approach-

int bigmod ( long long a, int p, int m )
{
    if ( p == 0 )return 1; // If power is 0 ( a ^ 0 ), return 1

    if ( p & 1 ) // If power is odd
    {
        return ( ( a % m ) * ( bigmod ( a, p - 1, m ) ) ) % m;
    }
    else
    {
        long long tmp = bigmod ( a, p / 2, m ); 
        return ( tmp * tmp ) % m;
    }
}

Big Mod Iterative approach-

long long bigmod ( long long a, long long p, long long m )
{
    long long res = 1;
    long long x = a;
    
    while ( p )
    {
        if ( p & 1 ) //p is odd
        {
            res = ( res * x ) % m;
        }
        x = ( x * x ) % m;
        p = p >> 1;
    }

    return res;
}

Factorial factorization

This function calculates the factorization of the given number's factorial.

int factors(int num)
{
    int i,tmp,cnt;
    
    for(i=0;i<max_prime && prime[i]<=num;i++)
    {
        cnt=0;
        tmp=num;
        cout<< prime[i] << " ";
        while(tmp>0)
        {
            cnt+=floor(tmp/prime[i]);
            tmp/=prime[i];
        }
        cout<< cnt << endl;
    }
}

Last non-zero digit of factorial

To find the last non-zero digit of a factorial number, the idea is to remove the extra zeroes in every step multiplying the numbers and don't need to hold the whole big number, just a small digit numbers from the last non-zero digits.
Here goes the code-

#include<stdio.h>
int main()
{
    long long int ans;
        int num;
        scanf("%d",&num);
 
        ans=1;
        for(int i=2;i<=num;i++)
        {
                ans=ans*i;
 
                while(ans%10==0)
                {
                        ans/=10;
                }
                ans%=10000000;
        }
        printf("%lld\n",ans%10);
 
        return 0;
}

Trailing zero in factorial

Finding number of trailing zero in factorial-

#include <stdio.h>
int main()
{
	int n,total,deno;
        scanf("%d",&n);
		
	total=0;
	deno=5;
	while(deno<=n)
	{
		total+=n/deno;
		deno*=5;
	}
	printf("%d\n",total);

	return 0;
}

Sum of Divisors of a Number

Sum of divisors of a Number can be found by the following formula.

Now the code. Following function calculate sum of divisors of a number-

#define i64 long long

i64 power(i64 N,i64 P)
{
	i64 sum=1,i;
	
	if(P==0)return 1;
	else
	{
		for(i=1;i<=P;i++)
			sum=sum*N;
		return sum;
	}
}

i64 sumofdivisor(i64 n)
{
	i64 sum=1,i,count;
	i64 sq=(i64)sqrt(n);
	
	for(i=0;prime[i]<=sq;i++)
	{
		count=0;
		while(n%prime[i]==0)
		{
			count++;
			n/=prime[i];
		}
		sum*=(i64)(power(prime[i],count+1)-1)/(prime[i]-1);
	}
	if(n>1)
		sum*=(n+1);
	return sum;
}

Bitwise sieve

Here is an implementation of Bitwise sieve. For full explanation See this and this-

#define MAX 100000000//max num to prime
#define LMT 10000 //sqrt(MAX)

int flag[MAX/64];
int prime[100000000],total;

#define chkC(n) (flag[n>>6]&(1<<((n>>1)&31)))
#define setC(n) (flag[n>>6]|=(1<<((n>>1)&31)))

void sieve() 
{
	unsigned i,j,k;

	flag[0]|=0;
	for(i=3;i<LMT;i+=2)
		if(!chkC(i))
			for(j=i*i,k=i<<1;j<MAX;j+=k)
				setC(j);

	prime[(j=0)++] = 2;//prime starts from 0 position
	for(i=3;i<MAX;i+=2)
		if(!chkC(i))
		{
			prime[j++] = i;
			//printf("%d\n",primes[j-1]);
		}
	total = j-1;
}

Number of divisor

To find the number of divisors of a number, first calculate find by sieve and then try this-

int number_of_divisor(int num)
{
 int j,count,div=1;
 for(j=0;prime[j]<=sqrt(num);j++) //prime array holds the prime numbers
 {
  count=0;
  while(num%prime[j]==0)
  {
   count++;
   num/=prime[j];
  }
  div*=(count+1);
 }
 if(num>1)
  div<<=1;
 return div;
}

This function returns the number of divisors of the given number.

Number of digits in factorial

This program calculate how many digit in factorial of the number in given base
Anyone can just calculate number of digits in decimal, then b=10 always.

#include <stdio.h>
#include <math.h>
int main()
{
	int number,i,base,digit;
	double c,a=0;

	printf("Give the base and the number: ");
	scanf ("%d%d",&base,&number);

	c=log10(base);
	for (i=number;i>=1;i--) {

		a+=(log10(i))/c; 
	}
	digit=a+1;
	printf ("%d\n",digit);

	return 0;
}

Sieve of Eratosthenes (Prime Finding)

The most popular prime finding method aka Sieve of Eratosthenes.

#define MAX 35000
#define lim 200

bool a[MAX];
int prime[MAX];

void sieve()
{
	int i,j;
	a[0]=1;a[1]=1;          //1 denotes not prime

	for(i=3;i<=lim;i+=2)    //even numbers are exclusive
	{
		if(a[i]==0)     //0 denotes prime
		{
			for(j=i*i;j < MAX;j+=i)
				a[j]=1;
		}
	}

	prime[0]=2;
	j=1;
	for(i=3;i < MAX;i+=2)     //even numbers are exclusive
	{
		if(a[i]==0)
			prime[j++]=i;
	}
}

Negative Base Conversion

Though, First time it may be a surprising fact that, "NEGATIVE BASE!!!", But it really exists. :)
Here goes it.Click Here for details.

NegaTernary(-3) Base conversion python implementation:

def negaternary(i):
    digits = []
    while i != 0:
        i, remainder = divmod(i, -3)
        if remainder < 0:
            i, remainder = i + 1, remainder + 3
        digits.insert(0, str (remainder))
    return ''.join(digits)

And Here is NegaBinary(-2) Base conversion in C:

#include<stdio.h>
int main()
{
	char a[100];
	int num,temp;

	while(~scanf("%d",&num))
	{
	while(num!=0)
	{
		temp=num%(-2);
		num/=(-2);
        if(temp < 0)
		{
			num+=1;
			temp+=2;
		}
		printf("%d ",temp);
	}
	puts("");
	}

	return 0;
}

GCD (Greatest Common Divisor)

Here are 3 different code for GCD, But the main Idea is always same-

//iterative gcd
int gcd ( int a, int b )
{
  int c;
  while ( b != 0 ) {
     c = b; b = a%b;  a = c;
  }
  return b;
}


//bitwise gcd
int gcd(int a, int b)
{

//actually this code is same as the previous
while(b) 
		b ^= a ^= b ^= a %= b;  //b^=a^=b^=a means swap(a,b)

return a;
}


//recursive gcd
int g_c_d(int a,int b)
{
	if(b==0)
		return a;
	else 
		return g_c_d(b,a%b);
}

Here is another short version of gcd using ternary operators:

int gcd ( int a, int b ) {
	return b ? gcd ( b, a % b ) : a ;
} 

Any Base Conversion

C++ implementation of Any Base to Any Base Conversion.

#include <cstdio>
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

#define all(x) x.begin(),x.end()

template<class t> inline t power(t num,t p)
{
    if(!p)    return 1;return (num*power(num,p-1));
}

bool islow(char ch){if(ch>='a' && ch<='z') return true; return false;}
bool isupp(char ch){if(ch>='A' && ch<='Z') return true; return false;}
bool isdig(char ch){if(ch>='0' && ch<='9') return true; return false;}

//any base to decimal conversion
int todec(string s,int base)
{
    int i,j,temp,len,sum=0;

    len=s.length()-1;
    for(i=0,j=len;i<=len;i++,j--)
    {
        char ch=s.at(i);
        if(isdig(ch))         temp=ch-'0';
        else if(islow(ch))    temp=10+ch-'a';
        else if(isupp(ch))    temp=10+ch-'A';

        sum+=(temp*(power(base,j)));
    }

    return sum;
}


//decimal to any base conversion
string tobase(int num,int base)
{
    int temp;
    string s;
    char ch;
    if(!num)    return "0"; //special '0' case handling

    while(num>0)
    {
        temp=num%base;
        num/=base;
        if(temp<=9) s+=(temp+'0');
        else        s+=((temp-10)+'A');
    }
    reverse(all(s));
    return s;
}

Binary to Decimal and Decimal to Binary conversion

Here is a short code for Binary to Decimal Conversion-

int to_dec(string str)
{
    int num=0,i;
    int mask=1;

    for(i=str.length()-1;i>=0;i--)
    {
        if(str.at(i)=='1')
            num|=mask;
        mask<<=1;
    }

        cout << num << endl;
    
    return num;
}

And a short code for Decimal to Binary Conversion-

string to_bin(int num)
{
    string str="";
    int mask=1;

    while(num)
    {
        if(num&mask)
            str="1"+str;
        else
            str="0"+str;

        num>>=1;
    }

    cout << str << endl;
    return str;
}

শুরুর কথা

আলাভোলার প্রোগ্রামিং ব্লগ যেমন আছে তেমনি থাকবে। ওখানে বিভিন্ন প্রোগ্রামিং আলোচনা, টিপস এবং বর্ণনামূলক ব্যাপার স্যাপারগুলো থাকবে।
আর এই ব্লগটা শুধুমাত্র 'কোড আর্কাইভ' হিসেবে ব্যবহার হবে। যাতে প্রয়োজনের সময় এই কোডগুলো কাজে লাগানো যায়।