dsalgo.MD

🌸 Data Structure and Algorithms in c++

[ Stanford : Algorithms, UCSD : Data Structure and Algorithms, ACM ICPC Bootcamp - C ]

Depth First Search (DFS) :

#include <iostream>
#include <vector>

// global declarations
// MAX is the maximum limit for the number of nodes (100,000).
const int MAX = 1e5;
// adjacency list
std::vector<int> adj[MAX];
std::vector<bool> visited;
std::vector<int> dp;

void depth_first_search(int u) {
    visited[u] = true;
    int child_height = 1;
    for (int v : adj[u]) {
        if (!visited[v]) {
            depth_first_search(v);

            // select maximum sub-tree height from all children.
            child_height = std::max(child_height, dp[v] + 1);
        }
    }
    // assigned the max child height to current visited node.
    dp[u] = child_height;
}

int main() {
    // number of nodes
    int number_of_nodes;
    std::cout << "Enter number of nodes of the tree : " << std::endl;
    std::cin >> number_of_nodes;

    // u, v denotes an undirected edge of tree.
    int u, v;
    // Tree contains exactly n-1 edges where n denotes the number of nodes.
    std::cout << "Enter edges of the tree : " << std::endl;
    for (int i = 0; i < number_of_nodes - 1; i++) {
        std::cin >> u >> v;
        // undirected tree u -> v and v -> u.
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    // initialize all nodes as unvisited.
    visited.assign(number_of_nodes + 1, false);
    // initialize depth of all nodes to 0.
    dp.assign(number_of_nodes + 1, 0);
    // function call which will initialize the height of all nodes.
    depth_first_search(1);
    std::cout << "Height of the Tree : " << dp[1] << std::endl;
}

DFS Function:

• depth_first_search(int u) is a recursive function to perform DFS starting from node u.
• Marks node u as visited.
• Initializes child_height to 1, representing the height of a single node.
• Iterates over all adjacent nodes v of u. If v is not visited, it recursively calls depth_first_search(v).
• Updates child_height to the maximum height found among all child nodes plus one (for the current node).
• Assigns the calculated child_height to dp[u], representing the height of the subtree rooted at node u.

Sorting and Searching	Data Structure [NOTES]
Sorting Algorithms [ vis, vid ] Bubble Sort Merge Sort Sorting Lower Bound Counting Sort Sorting in Practice Solving problems by sorting Sweep Line Algorithms Scheduling Events Tasks and Deadlines Binary Search [vid, vid2] Implementing the Search Finding Optimal Solutions	Dynamic Arrays Vectors Iterators and Ranges Other Structures Set Structures Sets and multisets [vid] Disjoint Set Union (DSU) / Union Find [blog, blog 2, Union Find Path Compression] Maps [vid] Priority Queues [vid] Policy-Based Sets Bitwise Operators Experiments: Set Versus Sorting Map Versus Array Priority Queue Versus Multiset
Dynamic Programming [NOTES]	Graph Algorithms [ NOTES ]
Basic Concepts When Greedy Fails [vid] Finding an Optimal Solution Counting Solutions Further Examples Longest Increasing Subsequence Paths in a Grid Knapsack Problems From Permutations to Subsets [blog] Counting Tilings [blog] [ How to Solve Any Dynamic Programming Problem ]	Basics of Graphs Graph Terminiology and Representation Graph Traversal Depth First Search (DFS) [ vid ] Breadth First Search (BFS) [ vid ] Applications Shortest Paths [A Comparison of Pathfinding Algorithms, (A*)] Bellman-Ford Algorithm [vid] Djikstra's Algorithm [vid] Floyd-Warshall Algorithm [ vid, vid2 ] Directed Acyclic Graphs [vid] Topological Sorting [vid - Kahn's Algorithm] Dynamic Programming Successor Graphs Finding Successors Cycle Detection Minimum Spanning Trees [ vid ] Kruskal's Algorithm [ vid ] Union-Find Structure [ vid, vid2, vid3 ] Prim's Algorithm [vid, vid2 - source_c vid] [The Definitive Guide to Graph Problems]
Algorithm design topics	Range Queries
Bit Parallel Algorithms Hamming Distances Counting Subgrids Reachability in Graphs Amortized Analysis Two Pointers method Nearest Smaller Elements Sliding Window Minimum Finding Minimum Vales Ternary Search Convex Functions Minimizing Sums	Queries on Static Arrays Sum Queries Minimum Queries Tree Structures Binary Indexed Trees (Fenwick Tree) [vid] Segment Trees [vid, p_list] Additional Techniques
Tree Algorithms [vid p_list]	Mathematics
Basic Techniques Tree Traversal [blog] Calculating Diameters All Longest Paths Tree Queries Finding Ancestors Subtrees and Paths Lowest Common Ancestors Merging Data Structures Advanced Techniques Centroid Decomposition [blog, blog2] Heavy-Light Deconmposition [blog]	Number Theory [notes] Primes and Factors Sieve of Erastosthenes Euclid's Algorithm Modular Exponentiation Euler's Theorem Solving Equations Combinatorics [notes] Binomial Coefficients Catalan Numbers Inclusion-Exclusion Burnside's Lemma Cayley's Formula Matrices [notes] Matrix Operations Linear Recurrences Graphs and Matrices Gaussian Elimination Probability [notes] Working with Events Random Variables Markov Chains Randomized Algorithms Game Theory [notes] Game States Nim Game Sprague-Grundy Theorem Fourier Transform [notes] Working with Polynomials FFT Algorithm Calculating Convolutions
Advanced Graph Algorithms [NOTES]	Geometry
Strong Connectivity Kosaraju's Algorithm [vid, vid2] 2SAT Problem Complete Paths Eulerian Paths Hamiltonian Paths Applications Maximum Flows Ford-Fulkerson Algorithm [ vid, source_c vid ] Disjoint Paths Maximum Matchings Path Covers Depth-First Search Trees Biconnectivity Eulerian Subgraphs Minimum Cost Flows [ vid ] Minimum Cost Paths Algorithm Minimum Weight Matchings Improving the Algorithm	Geometric Techniques [notes] Complex Numbers Points and Lines Polygon Area Distance Functions Sweep Line Algorithms [notes] Intersection Points Closest Pair Problem [vid] Convex Hull Problem [vid]
String Algorithms [ Knuth–Morris–Pratt KMP ]	Additional Topics
Basic Topics Trie Structure [vid, vid2] Dynamic Programming String Hashing Polynomial Hashing Applications Collisions and Parameters Z-Algorithm [vid] Constructing the Z-Array Applications Suffix Arrays [vid] Prefix Doubling Method Finding Patterns LCP Arrays String Automata Regular Languages Pattern Matching Automata Suffix Automata	Square Root Techniques Data Structures Subalgorithms Integer Partitions Mo's Algorithm [vid, vid2] Segment Trees Revisited Lazy Propagation Dynamic Trees Data Structures in Nodes Two-Dimensional Trees Treaps [vid] Splitting and Merging Implementation Additional Techniques Dynamic Programming Optimization Convex Hull Trick Divide and Conquer Optimization Knuth's Optimization Backtracking Techniques Prunning the Search Tree Heuristic Functions Miscellaneous Meet in the middle Counting Subsets Parallel Binary Search Dynamic Connectivity

resources: @github/cpp-ds-algorithms, Looking for a Challenge 2 Problems from the Polish Collegiate Programming Contest 2011–2014, Guide to Competitive Programming, Competitive Programmer’s Handbook, C/C++ cheatsheet Documentation, KTH Royal Institute of Technology Omogen Heap.