Problems Base course RU

Solves

connectivity

Articles

DS Data structure Disjoint set union Merge two sets and tell whether elements are in the same one, in almost O(1): a forest of parent links and two tricks. O(α(n)) 2 problems GRA Algorithm Depth-first search Goes deep, marks each vertex's entry and exit and finds cycles by them in O(V + E). O(V + E) 2 problems GRA Algorithm Bridges and articulation points Streets and crossroads without which a graph falls apart: one depth-first search with the numbers tin and low, O(V + E). O(V + E) 2 problems GRA Algorithm Dinic's algorithm Maximum flow in phases: a layered network, a blocking flow, pointers; O(V²E), and O(E√V) in unit networks. O(V² E) 2 problems

Problems

An import cycle Dark islands Night closures A crossing under repair Cuckoo nests Street closures Shortest itineraries with no change in common

Often together

classic 4 graph 3 maps and navigation 2 traversal 2 stack 2 interviews 2 networks 2 contests 2 disjoint sets 1 tree 1 array 1 amortized 1