Union Find

The disjoint-set data structure, also known as the union-find data structure, is used to keep track of a collection of non-overlapping sets or elements that are partitioned into disjoint subsets.

The primary operations associated with this data structure are:

• Find: Determine which subset an element belongs to. This is typically used to check if two elements are in the same subset.
• Union: Join two subsets together, combining them into a single subset.

The disjoint-set data structure is commonly used to solve problems that involve checking for connectivity between elements or managing partitions of sets. It's particularly efficient in applications like Kruskal's algorithm for finding minimum spanning trees, as it can quickly check if adding an edge would create a cycle in the graph.

A popular implementation of disjoint-set data structure is using an array or a map with a "parent" pointer for each element. The parent pointers are used to represent the tree structure that keeps track of the connected components. The efficiency of the find and union operations can be improved by applying path compression and union by rank heuristics.

Example

#include <iostream>
#include <vector>

class UnionFind {
public:
    UnionFind(int size) {
        parent.resize(size);
        rank.resize(size, 0);
        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) return;

        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootX] = rootY;
            if (rank[rootX] == rank[rootY]) {
                rank[rootY]++;
            }
        }
    }

private:
    std::vector<int> parent;
    std::vector<int> rank;
};

Past USACO Questions

• USACO 2019 January Contest, Silver Problem 1: MooTube
• USACO 2019 January Contest, Gold Problem 2: Mooriokart
• USACO 2018 December Contest, Gold Problem 1: New Barns
• USACO 2018 US Open Contest, Gold Problem 3: Out of Sorts