c++ - 标记为连接组件的列表表示

Question

我使用路径压缩（Sedgewick & Wayne）进行了加权快速联合，并填充了一个数组，比如说，id[i]，其中连接的组件根据不同的根放置。如果 id[i] == i，则 i 是根。如果不是，id[i] 是 i 的父级。我的问题是如何从这个数组中获取“连接组件列表（不同的根）”。我对如何找到每个 id 的根感到困惑，因为它们只指向直接父级。

以下是按 i 顺序排列的 id[i] 值（父母或祖父母）：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 757 57 5757

我的代码是：

    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]];
    }
    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; // return a list of connected components labelled
     }

///////////////////////////////////////////////////////////////////
I have managed to fix the above code as follows:

vector<vector<short>> components() { 
    vector<short> root, separated;
    vector<vector<short>> list; 
    for (int i = 0; i < id.size(); i++) id[i] = find(i); 
    for (int i = 0; i < id.size(); i++) if (i == id[i]) root.push_back(i);
    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; 
}

int find(int p) {
    while (p != id[p]) {
       id[p] = id[id[p]];    
       p = id[p];
    }
    return p;
}

现在它工作正常。

标签： c++