c++

 1. LCS-⭐ we will find answer through the way of generating all subsequences ------------ 1. Express everything in terms of indices 2. Explore all possibilities on that indices 3. take the best among them ---------- ------------------ a) Recursion Approach- 1. if char at i & j matches => do 1+f(i-1,j-1) 2. if char at i & j do not matches => do f(i-1,j) + f(i,j-1)   => explore both possibilities by moving 1 ptr at a time ---------------- b) Memoization ✅ -------------------- c) Tabulation -  since we can't write base case of recursion into tabulation with negative indices so we do a shifting of indices to right by 1 which means now f(i,j) will mean we want LCS of str1 till i-1 with str2 till j-1 we can also space optimize this solution using curr & prev vectors -------------------------------------------------------------------------------------------------------------------------- 2. Print LCS we will backtrack over dp table below is table we got...

1. Kosaraju's Algorithm- only for Directed graphs QUES - find no. of  strongly connected components (SCCs) & print them a strongly connected component is a component in which for every pair of nodes u,v we can go from u to v as well as from v to u OBSERVATION - 1. in original graph, we can traverse bidirectionally within a SCC & unidirectionally b/w SCCs 2. when we reverse direction b/w 2 SCCs , then we can traverse only within a SCC not b/w the 2 3. since we don't know where are SCCs so we reverse all the edges instead ---------------------------------------------------------------- ALGO- 1. sort all edges according to finishing time 2. reverse the graph 3. do dfs ------------------------------------------------------------- 1. do dfs from starting node, when u reach an end insert it into a stack, and backtrack & insert similarly for other branches as well 2. reverse the edges- simple 3. take st.top() and start dfs and mark nodes vis and store them one by one into ...

TOPICS- MST Prim's algo (greedy) DSU Kruskal Algo (using dsu) -------- No. of provinces        (no. of components in graph) Connected networks  (no. of extra edges in a component) Merged accounts       (dsu + hash map)⭐ no. of islands 2          (dsu + matrix) / (using size vector of dsu) stones removal          (dsu + treating each row & col as a node) --------------------------------------------------------------------------------------------------------------- Minimum Spanning Tree- 1. Spanning tree: has (n) nodes and (n-1) edges & all nodes are reachable from each other & do not has cycles 2. A graph can have any no. of spanning trees. 3. Out of all spanning trees, the tree with  min sum of all edge weights is called MST of a graph ---------------------------------------------------------------------------------------------------------------------------- Prim's Algo- time...