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;
    }
}