Union Find

Union Find

Link: GitHub

Module: Algorithms and Data Structures

Graduation Year: 2

The Union-Find data structure is an efficient way to keep track of the connected components of an undirected graph. (There are other applications of this data structure.) Its main operations are:
- [Union] Replace the connected components containing vertices p and q with their union (if the vertices belong to the same component, then there is nothing to do. Otherwise, merge the two components);
- [Find] Given a vertex p, find the vertex q that represents the connected component it belongs to. To keep the connectivity information of a graph updated for each edge insertion, perform a union operation of its incident vertices. Then, check if the two vertices are connected to verify if the representatives of the connected components are the same.
In the following example, an edge between vertices 1 and 2 is inserted into the graph. In this case, the corresponding union operation joins two connected components. One of the vertices of each connected component will be the representative vertex of that component. For a graph without edges, each vertex is the representative vertex of its component (each component has only one vertex). Each union operation causes the representative of the component of its second argument to become the representative of the first