Bellman Ford

Binary Search

Increasing Array lower_bound() returns value that is greater than or equal to x; upper_bound() returns value strictly greater than x; Decreasing array: lower_bound() returns value that is less than or equal to x; upper_bound() retruns value that is strictly less than x;

DFS Order

A very useful technique.It basically has 2 arrays one is Intime and the other is outTime. inTime says when it enters a recursion stack and outTime says when it exits the recursion stack. It is useful to check if a node v is present in the subtree of node u. If inTime[u]<inTime[v] and outTime[u]> outTime[v]. It can also be useful in counting number of nodes that belong to a particular tree at a particular height.

LCA

LCA Using Binary Lifting k=0 means the parent node Create a table P[K][N] -> N is number of nodes 2^k<=N So k<=logN Hence Size of table is N*logN jumps are made in order of powers of 2 ->1,2,4...etc trying to divide by 2 let mid=par[i][k-1] (2^(k-1)th parent if exists) par[i][k] is par[mid][k-1] Its basically dividing a big jump into 2. First make 2 nodes that we are going to find LCA to same depth using Walk function if current jump results -1 then we have jumped of the table.

Patience Sort

It is an online sorting algorithm aimed to create piles of cards in such a way that piles are in increasing order down wards. It can be used to find LIS in O(NlogN) time. Can also be used to find (minimum)number of distinct LIS. VII dp; for(int i=arr.size()-1;i>=0;--i) { int x=arr[i]; auto it=upper_bound(all(dp),x); if(it==dp.end()) dp.pb(x); else *it=x; } cout<<dp.size();

SCC

Kosaraju’s SCC A strongly Connected Component is for a directed graph. For an undirected graph we say it is a connected Component if we can reach a vertex from any vertex of a connected component. In case of SCC its same but called differently. Steps Perform DFS in forward graph and make a note of nodes in decreasing order of outtime. Perform DFS in reverse graph(instead of for loop use the decreasing order u found).