题解：
class Solution {
public:
vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) {
UnionFind uf;
for (auto& syn : synonyms) {
//cout << "syn:" << syn << endl;
auto syn_name = split_name(syn);
uf.add(syn_name.first);
uf.add(syn_name.second);
// 将这两个节点放入一个group
uf.merge(syn_name.first, syn_name.second);
}
//
std::unordered_map<std::string, std::set<People>> fathers;
std::unordered_map<std::string, int> fathers_count;
// 遍历所有名字
for (auto& name : names) {
People people;
split(name, people);
std::string father = uf.get_father(people.name);
// 获得父亲，并且按照字典序列进行排序
fathers[father].insert(people);
//cout << "nnnnn: " << people.name << endl;
// 统计按照group父亲节点，总数量
fathers_count[father] += people.count;
}
std::vector<std::string> result;
for (auto& father : fathers) {
// 获得字典序的第一个名字
std::string str = father.second.begin()->name;
//cout << "str:" << str << endl;
// 获得总数量
str = str + "(" + to_string(fathers_count[father.first]) + ")";
// 追加结果
result.push_back(str);
}
return result;
}
private:
struct People {
People() {
count = 0;
}
std::string name;
int count = 0;
// 按照字典序列进行排序
bool operator < (const People& people) const {
return name < people.name;
}
};
void split(string& str, People& people) {
auto it = str.find("(");
people.name = str.substr(0, it);
people.count = atoi(str.substr(it+1, str.size() - it -1).c_str());
//cout << "name: " << people.name << " count:" << people.count << endl;
}
std::pair<std::string, std::string> split_name(string& str) {
auto it = str.find(",");
std::pair<std::string, std::string> result;
result.first = str.substr(1, it-1);
result.second = str.substr(it+1, str.size() - it -1);
result.second.pop_back();
//cout << "first: " << result.first << " second:" << result.second << endl;
return result;
}
class UnionFind {
public:
void add(std::string& p) {
auto ite = _father.find(p);
if (ite == _father.end()) {
_father[p] = p;
}
}
void merge(std::string& p, std::string& q) {
std::string p_father = get_father(p);
std::string q_father = get_father(q);
if (p_father != q_father) {
_father[p_father] = q_father;
}
}
std::string get_father(std::string& _p) {
add(_p); //如果没有的节点，也要添加个节点
std::string p = _p;
while (_father[p] != p) {
p = _father[p];
}
return p;
}
std::unordered_map<std::string, std::string> _father;
};
};
