Disjoint-Set Data Structure
The Disjoint-Set Data Structure, also known as Union-Find, is used for keeping track of a set of elements partitioned into disjoint (non-overlapping) subsets. It supports two operations:
- Union: Join two subsets into a single subset.
- Find: Determine which subset an element belongs to.
Algorithm
- Initialization: Initialize
parent
array. For each element, the parent is itself. - Union: Merge two subsets by changing the parent of the root of one set to the root of the other.
- Find: Locate the root of a set for a given element. Update the parent pointers along the path.
Java Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public class DisjointSet {
private int[] parent;
public DisjointSet(int size) {
parent = new int[size];
for (int i = 0; i < size; i++) parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) parent[rootX] = rootY;
}
}
|
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <vector>
class DisjointSet {
public:
std::vector<int> parent;
DisjointSet(int size) : parent(size) {
for (int i = 0; i < size; ++i) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) parent[rootX] = rootY;
}
};
|
Python Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class DisjointSet:
def __init__(self, size):
self.parent = [i for i in range(size)]
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
self.parent[root_x] = root_y
# Example usage:
ds = DisjointSet(5)
ds.union(0, 2)
print(ds.find(2)) # Output: 0
|
The time complexity for the union and find operations is nearly (O(1)) when path compression and union by rank are used.