带路径压缩的加权Quick Union连通分量提取问题及修正方案

I was working with Sedgewick & Wayne's Weighted Quick Union algorithm with path compression, which produces an id array where:

• If id[i] == i, then i is a root node.
• Otherwise, id[i] is the direct parent of i.

My goal was to extract a list of connected components, where each component is a list of nodes sharing the same root. Here's the id array I was working with (indexes 0 to 159):

0 1 1 1 1 1 1 1 1 1 1 11 11 13 14 1 1 1 1 19 20 1 1 23 24 24 23 27 27 57 29 29 29 29 29 29 29 29 29 29 29 41 29 29 29 29 29 29 29 29 50 51 51 29 29 29 29 57 29 29 60 57 57 57 57 57 65 65 29 69 69 57 57 57 57 57 57 57 57 29 57 57 57 57 57 57 29 87 57 57 57 57 57 57 57 29 96 57 57 57 57 57 57 57 57 57 29 29 29 29 110 57 57 57 57 57 29 29 118 57 57 57 57 57 57 29 29 144 57 57 57 57 57 29 29 144 144 144 57 57 57 57 57 29 29 29 29 29 29 29 29 29 57 57 57 57 57 57 29 29 29 29 29 29 29 29 29 29 29 29 57 57 57 57 57 57 57

Initial (Flawed) Approach #

My first attempt didn't correctly group components because I only performed a single step of path compression instead of fully resolving each node to its root:

vector<vector<short>> components() {
    vector<short> root, separated;
    vector<vector<short>> list;
    for (int i = 0; i < id.size(); i++) {
        if (i == id[i]) root.push_back(i);
        else id[i] = id[id[i]]; // Only one step of path compression, not full root resolution
    }
    for (int j = 0; j < root.size(); j++) {
        separated.clear();
        for (int i = 0; i < id.size(); i++) {
            if (root[j] == id[i]) separated.push_back(i);
        }
        list.push_back(separated);
    }
    std::sort(list.begin(), list.end(), [](const vector<short> & a, const vector<short> & b) {
        return a.size() > b.size();
    });
    return list;
}

The issue here is that id[i] = id[id[i]] only moves a node up one level in the tree, not all the way to the root. This left many nodes still pointing to non-root parents, so when I checked root[j] == id[i], some nodes were incorrectly excluded from their component.

Corrected Working Solution #

I fixed this by implementing the full find function with path compression, which ensures every node's id entry directly points to its root. Then I collect roots and group nodes by their root:

vector<vector<short>> components() {
    // First, ensure every node points directly to its root using path compression
    for (int i = 0; i < id.size(); i++)
        id[i] = find(i);
    
    // Collect all unique root nodes
    vector<short> root;
    for (int i = 0; i < id.size(); i++)
        if (i == id[i])
            root.push_back(i);
    
    // Group nodes by their root to form components
    vector<vector<short>> list;
    vector<short> separated;
    for (int j = 0; j < root.size(); j++) {
        separated.clear();
        for (int i = 0; i < id.size(); i++) {
            if (root[j] == id[i])
                separated.push_back(i);
        }
        list.push_back(separated);
    }
    
    // Sort components by size descending
    std::sort(list.begin(), list.end(), [](const vector<short> & a, const vector<short> & b) {
        return a.size() > b.size();
    });
    
    return list;
}

// Find function with path compression to get the root of node p
int find(int p) {
    while (p != id[p]) {
        id[p] = id[id[p]]; // Path compression step (halve the path length)
        p = id[p];
    }
    return p;
}

Key Fixes Explained #

1. Full Root Resolution: By calling find(i) for every node, we ensure each id[i] is updated to point directly to its root. This makes grouping nodes by root straightforward.
2. Proper Root Collection: We collect roots only after all nodes have their root set, so we don't miss any roots or include non-root nodes as roots.
3. Correct Component Grouping: Now that every node's id points to its root, checking root[j] == id[i] correctly identifies all nodes in the component.

This solution now correctly extracts all connected components from the weighted Quick Union id array, sorted by component size in descending order.

内容的提问来源于stack exchange，提问作者deungsan