What Is Disjoint Set With Example in Data Structure?

What Is Disjoint Set With Example in Data Structure?

A disjoint set, also known as a union-find data structure, is a data structure that keeps track of a collection of disjoint sets. Each set has a representative element, which is usually one of the elements in the set. Disjoint sets are commonly used to solve problems related to connected components, such as finding cycles in an undirected graph or determining if two elements belong to the same set.

Operations on Disjoint Sets

There are three main operations that can be performed on disjoint sets:

• MakeSet(x): Creates a new set with x as its only element.
• Find(x): Returns the representative element of the set that x belongs to.
• Union(x, y): Combines two sets containing elements x and y into a single set.

The MakeSet Operation

The MakeSet operation creates a new set with a single element. In this operation, the representative element of the set is initially set to the element itself. For example:

DisjointSet ds;
ds.MakeSet(1);
ds.MakeSet(2);
ds.MakeSet(3);

The Find Operation

The Find operation returns the representative element of the set that an element belongs to. It can be used to determine whether two elements belong to the same set or not.

The Find operation uses path compression technique to optimize future Find operations. For example:

if (ds.Find(1) == ds.Find(2)) {
    System.out.println("1 and 2 belong to the same set");
} else {
    System.println("1 and 2 belong to different sets");
}

The Union Operation

The Union operation combines two sets into a single set. It finds the representative elements of the sets containing the given elements and makes one of them the parent of the other. For example:

ds.Union(1, 2);
ds.Union(2, 3);

After performing these operations, the sets {1, 2, 3} will be merged into a single set with representative element 1.

Example: Finding Cycles in an Undirected Graph

One practical application of disjoint sets is finding cycles in an undirected graph. Given a graph with n vertices and m edges, we can use disjoint sets to efficiently determine if the graph contains any cycles.

Here’s how it can be done:

1. Create a disjoint set for each vertex.
2. For each edge (u, v), where u and v are vertices in the graph:
• If Find(u) is equal to Find(v), then there is a cycle in the graph.
• Otherwise, perform Union(u, v) to merge the sets containing u and v.
3. If no cycles are found after processing all edges, then the graph is acyclic.

This algorithm works because when we encounter an edge (u, v), if both u and v already belong to the same set (i.e., they have the same representative element), then adding this edge would create a cycle. Otherwise, we merge the two sets using Union(u, v).

Note: The time complexity of the Union operation in disjoint sets is typically O(log n) or even O(α(n)), where α(n) is the inverse Ackermann function. The time complexity of the Find operation is also O(log n) or O(α(n)).

By using disjoint sets, we can efficiently solve problems related to connected components and cycles in graphs. It provides a powerful tool for solving various data structure and algorithm problems.