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