程序员面试金典 - 面试题 17.07. 婴儿名字（并查集）_面试题获取宝宝年月程序员-CSDN博客

本文链接：https://blog.csdn.net/qq_21201267/article/details/105300614

本文介绍了一种使用并查集数据结构解决婴儿名字频率统计问题的方法。通过将同义名字进行合并，实现对真实名字实际频率的准确计算。文章详细展示了算法流程与实现代码，适用于处理大规模名字数据的场景。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

1. 题目

每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。
有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。

给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。
设计一个算法打印出每个真实名字的实际频率。
注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。

在结果列表中，选择字典序最小的名字作为真实名字。

示例：
输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], 
synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
输出：["John(27)","Chris(36)"]

提示：
names.length <= 100000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/baby-names-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

参考：并查集（Disjoint-Set）

class Solution {
    unordered_map<string,string> father;//并查集
    unordered_map<string,int> m;//名称，频次
public:
    vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) {
        string name, name1, name2, p;
        int i, count;
        for(string& n : names)
        {
            i = n.find("(");
            name = n.substr(0,i);
            count = 0;
            while(++i < n.size()-1)
                count = 10*count+n[i]-'0';
            m[name] = count;//获取每个名字的次数
            father[name] = name;//并查集初始化
        }
        for(auto& n : synonyms)
        {   //这里可能有上面不存在的name，再添加一遍
            i = n.find(",");
            name1 = n.substr(1,i-1);
            name2 = n.substr(i+1,n.size()-i-2);
            father[name1] = name1;//并查集初始化
            father[name2] = name2;//并查集初始化
        }
        for(auto& n : synonyms)
        {
            i = n.find(",");
            name1 = n.substr(1,i-1);
            name2 = n.substr(i+1,n.size()-i-2);
            merge(name1,name2);//全部进行合并和路径压缩
        }
        unordered_map<string,vector<string>> fatherSet;
        for(auto f : father)//压缩后的f(只有两层)，所有边的顶层（字典序最小的）
        {
            name = f.first;
            p = uniFind(name);
            fatherSet[p].push_back(name);
        }
        vector<string> ans;
        for(auto& f : fatherSet)
        {	//所有的等效名字
            count = 0;
            for(auto& v : f.second)//它底下包含的name
                count += m[v];//加上他的计数
            ans.push_back(f.first+"("+to_string(count)+")");
        }
        return ans;
    }

    string uniFind(string x)
    {
        if(x == father[x])
            return x;
        return father[x] = uniFind(father[x]);//等式为路径压缩操作
    }

    void merge(string x, string y)
    {
        string fatherx = uniFind(x);
        string fathery = uniFind(y);
        if(fatherx != fathery)
        {
            if(fatherx < fathery)
                swap(fatherx, fathery);//x的字典序大
            father[fatherx] = fathery;//字典序小的y做代表
        }
    }
};