Understanding Union-Find

Union-Find is a data structure designed to manage relationships between sets, enabling operasions like determining set membership and merging distinct sets.

Consider a practical scenario: Initially, Xiao Ming belongs to one family set and Xiao Hong to another. When they marry (merge operation), they form a single family (one set). Union-Find facilitates such set unions and provides efficient membership checks.

Core Operations

Union Operation: Merges two separate sets by connecting their root elements. Each set has exactly one root node, where the root's parent points to itself since it has no ancestor.

Find Operation: Determines the root element for any node. To find node 3's root, we recursive follow parent pointers until reaching the root. Without optimization, this takes O(log n) time proportional to tree height. For frequent queries, path compression becomes essential.

Path compression optimizes subsequent finds by flatttening the tree during the first query. While the initial query takes height steps, subsequent queries achieve near-constant time complexity.

Basic Implementation

#include<iostream>
using namespace std;

const int MAX_NODES = 100010;
int parent[MAX_NODES];

int findRoot(int node) {
    if (parent[node] != node) {
        parent[node] = findRoot(parent[node]);
    }
    return parent[node];
}

int main() {
    int nodeCount, operationCount;
    cin >> nodeCount >> operationCount;
    
    for (int i = 1; i <= nodeCount; i++) {
        parent[i] = i;
    }
    
    while (operationCount--) {
        char operation;
        int first, second;
        cin >> operation >> first >> second;
        
        if (operation == 'M') {
            parent[findRoot(first)] = findRoot(second);
        } else {
            if (findRoot(first) == findRoot(second)) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }
    }
    return 0;
}

Initialization ensures each node starts as its own root. The union operation connects sets by making one root point to another. Find operations check set membership by comparing roots.

Union-Find Variations

Beyond the basic implementation, two important variations exist: Weighted Union-Find and Extended Domain Union-Find. These enhance the standard structure with additional capabilities.

Weighted Union-Find

This variation extends standard Union-Find by maintaining and considering weights, which could represent tree height, set size, or other numerical properties.