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...

# Note - 1. SCC : - only for directed graphs - strongly connected component (  component in which for every pair of nodes u,v we can go from u to v as well as from v to u ) -  In a graph having SCCs, we can traverse bidirectionally within a SCC & unidirectionally b/w SCCs. But,  when we reverse the graph, then we can traverse only within a SCC not b/w adjacent ones   ---------- 2. Kosaraju and Tarjan Algo are used to find SCCs 3. Applications include finding deadlocks, clusters, echo chambers, dependency cycle, etc. ------------------------------ 4.  Bridges : - only for undirected graphs - they are edges which if removed disconnects the graph. 5. Articulation points : They are node which if removed (along with all its edges) disconnects the graph. 6. Applications include network resilience analysis, thus finding critical node and edge. 7. If discovery time(node B) < disc(A) => B is ancestor of node A 8. disc[curr node] = disc[last visited node] +...

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- - MST gives set of edges, such that we  connect all nodes in a network with min total cost - For an MST to exist- graph must be connected, undirected, weighted, has no cycles, has n-1 edges - A graph can have multiple spanning trees.  Out of all, one with  min sum of all edge weights is called MST of the graph ---------------------------------------------------------------------------------------------------------------------------- # Prim's Algo- (greedy) tim...