基于字符串的并查集（Disjoint Union）实现求助：代码调试与资料参考

我有一个固定尺寸为2的vector<vector<string>>类型变量equations，每个equations[i]是类似{"Hi", "I am"}的字符串对。需要对每对字符串执行不相交集合（并查集）操作，最终获取每个字符串的父节点。用map实现后多个测试用例失败，比如输入{{"a","b"},{"b","c"},{"a","d"}}时，所有元素的父节点应该指向同一集合的根节点（比如"a"）。以下是我的实现代码：

map<string,int> siz;
string &find(map<string,string> &mp,string &a)
{
    if(mp[a]==a)
        return a;
    return mp[a]=find(mp,mp[a]);
}
void Union(map<string,string> &mp,string &a,string &b)
{
    a=find(mp,a);
    b=find(mp,b);
    if(a==b)
        return;
    else
    {
        if(siz[a]>siz[b])
        {
            mp[b]=a;
            siz[a]+=siz[b];
        }
        else
        {
            mp[a]=b;
            siz[b]+=siz[a];
        }
    }
}
void get_parent(vector<vector<string>> &equations,vector<string> &ele)
{
    map<string,string> parent;
    for(int i=0;i<equations.size();i++)
    {
        parent[equations[i][0]]=equations[i][0];
        parent[equations[i][1]]=equations[i][1];
        siz[equations[i][0]]=1;
        siz[equations[i][1]]=1;
    }
    for(int i=0;i<equations.size();i++)
    {
        Union(parent,equations[i][1],equations[i][0]);
    }
    for(int i=0;i<ele.size();i++)
        cout<<(parent[ele[i]]);
}

原代码问题分析 #

• 全局siz变量污染：如果多次调用get_parent，全局siz会保留之前测试用例的数据，导致合并逻辑错误。
• find函数引用风险：递归返回引用时可能出现临时对象引用失效的情况，且未处理元素不存在的场景。
• Union函数参数副作用：直接修改传入的字符串引用，会改变原变量的值，属于不必要的操作。
• 初始化重复覆盖：循环中重复设置同一元素的父节点和大小，虽然不影响结果，但存在冗余。
• 输出未做路径压缩：直接输出parent[ele[i]]可能得到的不是最终根节点，因为部分元素的路径压缩未完成。

修正后的可运行代码 #

#include <iostream>
#include <vector>
#include <map>
#include <string>

using namespace std;

// 查找根节点，带路径压缩
string find(map<string, string>& parent, const string& a) {
    if (parent[a] != a) {
        parent[a] = find(parent, parent[a]);
    }
    return parent[a];
}

// 按秩合并
void Union(map<string, string>& parent, map<string, int>& siz, const string& a, const string& b) {
    string rootA = find(parent, a);
    string rootB = find(parent, b);
    if (rootA == rootB) {
        return;
    }
    // 小秩树合并到大秩树下，保持树的平衡
    if (siz[rootA] > siz[rootB]) {
        parent[rootB] = rootA;
        siz[rootA] += siz[rootB];
    } else {
        parent[rootA] = rootB;
        siz[rootB] += siz[rootA];
    }
}

void get_parent(vector<vector<string>>& equations, vector<string>& ele) {
    map<string, string> parent;
    map<string, int> siz; // 改为局部变量，避免跨用例数据污染

    // 初始化元素，避免重复设置
    for (auto& pair : equations) {
        const string& s1 = pair[0];
        const string& s2 = pair[1];
        if (parent.find(s1) == parent.end()) {
            parent[s1] = s1;
            siz[s1] = 1;
        }
        if (parent.find(s2) == parent.end()) {
            parent[s2] = s2;
            siz[s2] = 1;
        }
    }

    // 执行合并操作
    for (auto& pair : equations) {
        Union(parent, siz, pair[0], pair[1]);
    }

    // 输出每个元素的根节点，输出前确保路径压缩完成
    for (auto& e : ele) {
        if (parent.count(e)) {
            cout << find(parent, e) << " ";
        } else {
            cout << "[不存在] ";
        }
    }
    cout << endl;
}

// 测试示例
int main() {
    vector<vector<string>> equations = {{"a","b"},{"b","c"},{"a","d"}};
    vector<string> ele = {"a", "b", "c", "d"};
    get_parent(equations, ele); // 输出应为 a a a a（或同一集合的任意根节点）
    return 0;
}

代码关键优化点 #

1. 将siz改为局部变量，彻底解决多测试用例的数据污染问题。
2. find函数使用const string&参数，避免不必要的拷贝，同时保证路径压缩逻辑正确。
3. Union函数用临时变量存储根节点，不再修改原始输入字符串，消除副作用。
4. 初始化时检查元素是否已存在，避免重复赋值。
5. 输出前再次调用find，确保所有元素都完成路径压缩，输出的是最终根节点。
6. 增加对ele中不存在元素的处理，避免输出错误内容。

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