Dynamic connectivity involves maintaining connectivity information in a changing graph. It's often solved using data structures like Union-Find or dynamic trees.

Dynamic connectivity is a common problem in competitive programming that involves maintaining information about the connected components of a graph as edges are added or removed over time. In static connectivity problems, you are typically given a fixed graph, and the task is to determine whether two nodes are connected or to find the connected components. In dynamic connectivity, however, the graph changes dynamically as edges are added or removed, and you need to update the connectivity information efficiently. One of the most widely used data structures for solving dynamic connectivity problems is the Union-Find (or Disjoint Set Union, DSU) data structure. Union-Find allows you to quickly determine whether two nodes are in the same connected component and to merge (union) two components when a new edge is added. With path compression and union by rank optimizations, Union-Find operations can be performed in nearly constant time. For more complex dynamic connectivity problems, such as those that involve deleting edges or maintaining minimum spanning trees, more advanced data structures like dynamic trees (also known as link-cut trees) may be required. These data structures allow you to efficiently update and query the connectivity of the graph as it evolves. Understanding dynamic connectivity is important in competitive programming for solving problems related to road networks, social networks, and dynamic graphs in general.