repository·master·Indexed 26 days ago
https://github.com/ebtech/rust-algorithmsA collection of classic data structures and algorithms implemented in Rust, designed as a 'whitebox cookbook' for students, educators, and competitive programmers. The library includes implementations for graph theory (connectivity, network flows, 2-SAT), mathematics (number theory, FFT, linear algebra), string processing (Trie, KMP, Aho-Corasick), associative range queries (ARQ), and search/ordering utilities. It also provides a Scanner for ergonomic I/O and a Cacher for memoization.
contest-algorithms crate is a collection of classic data structures and algorithms implemented in Rust. It is designed as a 'whitebox cookbook' rather than a blackbox library, prioritizing usability, clarity, and conciseness to help students, educators, and competitive programmers. The implementations are optimized for being easy to modify under time pressure in programming contests.Scanner module provides a utility for reading input data ergonomically, including support for both file and standard I/O, which is useful for competitive programming environments.The repository contains implementations for several algorithmic domains:
lower_bound/upper_bound), Merge sort, Coordinate compression, Online convex hull trick.u, use the adj_list(u) method. This returns an AdjListIterator which yields tuples of (edge_id, destination_vertex_id).StaticArq::new(init_val) to create a static balanced binary tree (often called a segment tree) from an initial sequence of elements. The tree requires a type T that implements the ArqSpec trait to define the monoid operations and endomorphisms.PiecewiseLinearConvexFn represents the maximum (upper envelope) of a collection of linear functions. It uses an online version of the convex hull trick with square root decomposition for efficient amortized performance.
max_with(new_m, new_b): Adds a new line with slope new_m and intercept new_b to the collection.evaluate(x): Evaluates the current maximum function at point x with good amortized runtime.The ConnectivityGraph struct provides several methods to query the connectivity properties of the graph it was initialized with:
cc: A Vec<usize> where cc[u] is the ID of vertex u's component (CC, SCC, or 2ECC). IDs range from 1 to num_cc.vcc: A Vec<usize> where vcc[e] is the ID of edge e's 2VCC. IDs range from 1 to num_vcc.num_cc: The total number of CCs, SCCs, or 2ECCs.num_vcc: The total number of 2VCCs.is_cut_vertex(u: usize) -> bool: Returns true if vertex u is an articulation vertex in an undirected graph.is_cut_edge(e: usize) -> bool: Returns true if edge e is a bridge in an undirected graph.The z_algorithm(text) function computes the Z-array in $O(n)$ time. For each index i, Z[i] is the length of the longest prefix of text[i..] that is also a prefix of the entire text.
use contest_algorithms::string_proc::z_algorithm;
let z = z_algorithm(b"ababbababbabababbabababbababbaba");The dinic(s, t) method implements Dinic's algorithm to find the maximum flow from source s to sink t (where s != t). It generalizes the Hopcroft-Karp algorithm for bipartite matching.
Returns a tuple (max_flow, flow) where:
max_flow: The total amount of flow.flow: A Vec<i64> containing the flow assigned to each edge index.Panics if the maximum flow is $2^{63}$ or larger.
SparseIndex is a data structure used for coordinate compression.
SparseIndex::new(coords) where coords is a Vec<i64> of all possible coordinates..compress(q) to find the compressed index of a coordinate q.compress returns:
Ok(i) if the coordinate q exists exactly at index i.Err(i) if q falls between indices i-1 and i (useful for range queries).query(l, r) to return the aggregate value of the range [l, r] inclusive based on the monoid operation defined in the ArqSpec.