How do I implement disjoint set union (union-find) in C++?

The Disjoint Set Union (DSU), also known as Union-Find, is a data structure that keeps track of a partition of a set into disjoint subsets. It provides efficient methods for union and find operations, making it useful for various applications like network connectivity, Kruskal's algorithm for finding the minimum spanning tree, and more.

Implementation of Disjoint Set Union (Union-Find) in C++

Below is a simple implementation of the Disjoint Set Union data structure in C++:

#include #include class DisjointSet { private: std::vector parent, rank; public: DisjointSet(int size) { parent.resize(size); rank.resize(size, 0); for (int i = 0; i < size; ++i) { parent[i] = i; // Each element is its own parent } } int find(int u) { if (parent[u] != u) { parent[u] = find(parent[u]); // Path compression } return parent[u]; } void unionSet(int u, int v) { int rootU = find(u); int rootV = find(v); if (rootU != rootV) { if (rank[rootU] < rank[rootV]) { parent[rootU] = rootV; } else if (rank[rootU] > rank[rootV]) { parent[rootV] = rootU; } else { parent[rootV] = rootU; rank[rootU]++; } } } }; int main() { DisjointSet ds(10); // Create a disjoint set with 10 elements ds.unionSet(1, 2); ds.unionSet(2, 3); std::cout << "The representative of set containing 2: " << ds.find(2) << std::endl; std::cout << "The representative of set containing 3: " << ds.find(3) << std::endl; return 0; }

Disjoint Set Union Union-Find C++ Data Structures Path Compression Kruskal's Algorithm

Related Questions

How do I avoid rehashing overhead with std::set in multithreaded code?

How do I find elements with custom comparators with std::set for embedded targets?

How do I erase elements while iterating with std::set for embedded targets?

How do I provide stable iteration order with std::unordered_map for large datasets?

How do I reserve capacity ahead of time with std::unordered_map for large datasets?

How do I erase elements while iterating with std::unordered_map in multithreaded code?

How do I provide stable iteration order with std::map for embedded targets?

How do I provide stable iteration order with std::map in multithreaded code?

How do I avoid rehashing overhead with std::map in performance-sensitive code?

How do I merge two containers efficiently with std::map for embedded targets?