When to Use Disjoint Set Union (DSU) Beyond Graphs

Introduction

Most developers know Disjoint Set Union (DSU) for graph connectivity problems. But DSU's true power extends far beyond—from dynamic connectivity queries to offline algorithm optimization and creative problem transformations.

This guide reveals advanced DSU techniques that can transform seemingly impossible problems into elegant O(α(n)) solutions.

DSU Fundamentals Recap

Optimized Implementation

class DSU {
    vector parent, rank;
    int components;
    
public:
    DSU(int n) : parent(n), rank(n, 0), components(n) {
        iota(parent.begin(), parent.end(), 0);
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }
    
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        
        // Union by rank
        if (rank[px] < rank[py]) swap(px, py);
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        
        components--;
        return true;
    }
    
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
    
    int getComponents() const { return components; }
};

Advanced DSU Applications

1. Dynamic Connectivity with Rollback

For problems requiring edge removal or "what-if" scenarios:

class RollbackDSU {
    vector parent, rank;
    stack>> history; // {node, {old_parent, old_rank}}
    
public:
    RollbackDSU(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    
    int find(int x) {
        while (parent[x] != x) x = parent[x]; // No path compression!
        return x;
    }
    
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) {
            history.push({-1, {-1, -1}}); // Mark no-op
            return;
        }
        
        if (rank[x] < rank[y]) swap(x, y);
        
        // Save state before modification
        history.push({y, {parent[y], rank[x]}});
        
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
    
    void rollback() {
        auto [node, state] = history.top();
        history.pop();
        
        if (node == -1) return; // No-op
        
        auto [old_parent, old_rank] = state;
        parent[node] = old_parent;
        
        int root = find(node);
        if (old_rank != rank[root]) {
            rank[root] = old_rank;
        }
    }
};
// Application: Dynamic Graph Connectivity
class DynamicConnectivity {
    RollbackDSU dsu;
    
public:
    DynamicConnectivity(int n) : dsu(n) {}
    
    bool queryWithTemporaryEdge(int u, int v, int x, int y) {
        dsu.unite(u, v);           // Add temporary edge
        bool result = dsu.find(x) == dsu.find(y);
        dsu.rollback();            // Remove edge
        return result;
    }
};

2. Offline Query Processing

Transform online queries into offline batch processing:

struct Query {
    int type; // 0: add edge, 1: query connectivity
    int u, v;
    int id;   // Original query order
};
vector processConnectivityQueries(int n, vector& queries) {
    DSU dsu(n);
    vector results(queries.size());
    
    // Sort queries: edges first, then connectivity queries
    sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
        return a.type < b.type;
    });
    
    for (const Query& q : queries) {
        if (q.type == 0) {
            dsu.unite(q.u, q.v);
        } else {
            results[q.id] = dsu.connected(q.u, q.v);
        }
    }
    
    return results;
}

3. DSU on Trees - Subtree Queries

Solve tree problems using DSU with DFS:

class TreeDSU {
    vector> adj;
    vector subtreeSize;
    DSU dsu;
    
public:
    TreeDSU(int n) : adj(n), subtreeSize(n), dsu(n) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void dfs(int u, int parent) {
        subtreeSize[u] = 1;
        
        for (int v : adj[u]) {
            if (v != parent) {
                dfs(v, u);
                subtreeSize[u] += subtreeSize[v];
                dsu.unite(u, v); // Merge subtrees
            }
        }
        
        // Process queries for subtree rooted at u
        processSubtreeQueries(u);
    }
    
private:
    void processSubtreeQueries(int root) {
        // All nodes in subtree are now in same DSU component
        int componentRoot = dsu.find(root);
        // Process queries involving this subtree
    }
};

Creative Problem Transformations

1. Grid Connectivity with Obstacles

class GridDSU {
    DSU dsu;
    int rows, cols;
    vector> blocked;
    
    int getIndex(int r, int c) {
        return r * cols + c;
    }
    
public:
    GridDSU(int r, int c) : rows(r), cols(c), dsu(r * c), blocked(r, vector(c, false)) {}
    
    void addObstacle(int r, int c) {
        blocked[r][c] = true;
        
        // Disconnect from neighbors
        vector> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        for (auto [dr, dc] : dirs) {
            int nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !blocked[nr][nc]) {
                // Note: DSU doesn't support disconnection directly
                // Use alternative approach or rebuild DSU
            }
        }
    }
    
    void removeObstacle(int r, int c) {
        blocked[r][c] = false;
        
        // Connect to unblocked neighbors
        vector> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        for (auto [dr, dc] : dirs) {
            int nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !blocked[nr][nc]) {
                dsu.unite(getIndex(r, c), getIndex(nr, nc));
            }
        }
    }
    
    bool isConnected(int r1, int c1, int r2, int c2) {
        if (blocked[r1][c1] || blocked[r2][c2]) return false;
        return dsu.connected(getIndex(r1, c1), getIndex(r2, c2));
    }
};

2. Range Union Queries

class RangeDSU {
    map ranges; // start -> end mapping
    
public:
    void addRange(int start, int end) {
        auto it = ranges.upper_bound(start);
        
        // Check if we can merge with previous range
        if (it != ranges.begin()) {
            --it;
            if (it->second >= start - 1) {
                start = min(start, it->first);
                end = max(end, it->second);
                ranges.erase(it);
            } else {
                ++it;
            }
        }
        
        // Merge with overlapping ranges
        while (it != ranges.end() && it->first <= end + 1) {
            end = max(end, it->second);
            it = ranges.erase(it);
        }
        
        ranges[start] = end;
    }
    
    bool inSameRange(int x, int y) {
        auto it = ranges.upper_bound(x);
        if (it != ranges.begin()) {
            --it;
            if (it->second >= x && it->first <= y && it->second >= y) {
                return true;
            }
        }
        return false;
    }
};

Performance Optimizations

1. Memory-Efficient DSU

class CompactDSU {
    vector parent;
    vector rank; // Use smaller data type
    
public:
    CompactDSU(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    
    // Same operations but 75% less memory usage
};

2. Batch Processing Optimization

class BatchDSU {
    DSU dsu;
    vector> pendingUnions;
    
public:
    BatchDSU(int n) : dsu(n) {}
    
    void scheduleUnion(int x, int y) {
        pendingUnions.push_back({x, y});
    }
    
    void processBatch() {
        // Sort to improve cache locality
        sort(pendingUnions.begin(), pendingUnions.end());
        
        for (auto [x, y] : pendingUnions) {
            dsu.unite(x, y);
        }
        
        pendingUnions.clear();
    }
};

Real-World Applications

1. Social Network Analysis

class SocialNetwork {
    DSU friendGroups;
    unordered_map userToId;
    vector idToUser;
    
public:
    SocialNetwork() : friendGroups(0) {}
    
    int addUser(const string& username) {
        if (userToId.find(username) != userToId.end()) {
            return userToId[username];
        }
        
        int id = idToUser.size();
        userToId[username] = id;
        idToUser.push_back(username);
        
        // Expand DSU
        friendGroups = DSU(id + 1);
        return id;
    }
    
    void addFriendship(const string& user1, const string& user2) {
        int id1 = addUser(user1);
        int id2 = addUser(user2);
        friendGroups.unite(id1, id2);
    }
    
    bool areInSameFriendGroup(const string& user1, const string& user2) {
        auto it1 = userToId.find(user1);
        auto it2 = userToId.find(user2);
        
        if (it1 == userToId.end() || it2 == userToId.end()) {
            return false;
        }
        
        return friendGroups.connected(it1->second, it2->second);
    }
    
    int getFriendGroupSize(const string& username) {
        auto it = userToId.find(username);
        if (it == userToId.end()) return 0;
        
        int root = friendGroups.find(it->second);
        int count = 0;
        
        for (int i = 0; i < idToUser.size(); i++) {
            if (friendGroups.find(i) == root) {
                count++;
            }
        }
        
        return count;
    }
};

2. Image Processing - Connected Components

class ImageProcessor {
    GridDSU dsu;
    
public:
    ImageProcessor(int height, int width) : dsu(height, width) {}
    
    int countConnectedRegions(vector>& image, int threshold) {
        int rows = image.size(), cols = image[0].size();
        DSU regionDSU(rows * cols);
        
        auto getIndex = cols { return r * cols + c; };
        
        // Connect similar adjacent pixels
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                // Check right neighbor
                if (c + 1 < cols && abs(image[r][c] - image[r][c+1]) <= threshold) {
                    regionDSU.unite(getIndex(r, c), getIndex(r, c+1));
                }
                
                // Check bottom neighbor
                if (r + 1 < rows && abs(image[r][c] - image[r+1][c]) <= threshold) {
                    regionDSU.unite(getIndex(r, c), getIndex(r+1, c));
                }
            }
        }
        
        return regionDSU.getComponents();
    }
};

Common Mistakes & Pitfalls

❌ Mistake 1: Path Compression with Rollback

// Wrong - path compression breaks rollback
class BadRollbackDSU {
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Modifies structure!
        }
        return parent[x];
    }
};
// Correct - use iterative find for rollback DSU
int find(int x) {
    while (parent[x] != x) x = parent[x];
    return x;
}

❌ Mistake 2: Ignoring Amortized Complexity

// Don't assume every operation is O(1)
// α(n) is practically constant but still grows
// For time-critical applications, consider:
if (n > 1000000) {
    // Use alternative data structure
    // or batch operations
}

❌ Mistake 3: Incorrect Union by Rank

// Wrong - always attach smaller to larger
void badUnite(int x, int y) {
    parent[y] = x; // Ignores rank!
}
// Correct - maintain rank invariant
void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    
    if (rank[x] < rank[y]) swap(x, y);
    parent[y] = x;
    if (rank[x] == rank[y]) rank[x]++;
}

Complexity Analysis

Where α(n) is the inverse Ackermann function, practically ≤ 4 for all realistic inputs.

Advanced Techniques Summary

Conclusion

DSU's versatility extends far beyond graph connectivity. Master these advanced techniques:

- Rollback DSU for dynamic scenarios - Offline processing for query optimization - Creative transformations for non-obvious problems - Memory optimizations for large datasets

Key Insights: - Choose the right DSU variant for your problem - Consider offline processing for better complexity - Don't forget about practical constant factors

Practice These Applications: - Dynamic Connectivity Queries - Social Network Analysis - Image Segmentation

--- *Master advanced data structures and unlock new problem-solving approaches. Start practicing today!*