This representative is an element of its corresponding set. find_set(v) - returns the representative (also called leader) of the set that contains the element v.union_sets(a, b) - merges the two specified sets (the set in which the element a is located, and the set in which the element b is located).make_set(v) - creates a new set consisting of the new element v.Thus the basic interface of this data structure consists of only three operations: The classical version also introduces a third operation, it can create a set from a new element. We are given several elements, each of which is a separate set.Ī DSU will have an operation to combine any two sets, and it will be able to tell in which set a specific element is. This data structure provides the following capabilities. Often it is also called Union Find because of its two main operations. This article discusses the data structure Disjoint Set Union or DSU. The Stern-Brocot Tree and Farey Sequences Optimal schedule of jobs given their deadlines and durationsġ5 Puzzle Game: Existence Of The Solution MEX task (Minimal Excluded element in an array) Search the subsegment with the maximum/minimum sum RMQ task (Range Minimum Query - the smallest element in an interval) Kuhn's Algorithm - Maximum Bipartite Matching Maximum flow - Push-relabel algorithm improved Maximum flow - Ford-Fulkerson and Edmonds-Karp Lowest Common Ancestor - Tarjan's off-line algorithm Lowest Common Ancestor - Farach-Colton and Bender algorithm Second best Minimum Spanning Tree - Using Kruskal and Lowest Common AncestorĬhecking a graph for acyclicity and finding a cycle in O(M) Minimum Spanning Tree - Kruskal with Disjoint Set Union Number of paths of fixed length / Shortest paths of fixed length Strongly Connected Components and Condensation Graphĭijkstra - finding shortest paths from given vertexīellman-Ford - finding shortest paths with negative weightsįloyd-Warshall - finding all shortest paths Half-plane intersection - S&I Algorithm in O(N log N)Ĭonnected components, bridges, articulations points Search for a pair of intersecting segmentsĭelaunay triangulation and Voronoi diagram Pick's Theorem - area of lattice polygons Manacher's Algorithm - Finding all sub-palindromes in O(N)īurnside's lemma / Pólya enumeration theoremįinding the equation of a line for a segmentĬheck if points belong to the convex polygon in O(log N) Storing the DSU by maintaining a clear tree structure / Online bridge findingĭeleting from a data structure in O(T(n) log n)ĭynamic Programming on Broken Profile. Storing the DSU explicitly in a set list / Applications of this idea when merging various data structures Support the parity of the path length / Checking bipartiteness online
Path finder algorithm java Offline#
Store additional information for each setĬompress jumps along a segment / Painting subarrays offline Search for connected components in an image Euclidean algorithm for computing the greatest common divisor
0 kommentar(er)
