如何设计数据结构实现字符串等价关系与团队总分计算

现有一组<string, string>类型的等价关系对：[("Player1", "Player2"), ("Player3", "Player4"), ("Player2", "Player3"), ("Player11", "Player13")]，表示关联玩家同属一个团队；另有一组<string, int>类型的分数对：[("Player1", 50), ("Player3", 25)]，需求是计算指定玩家所在团队的总分（本例中Player1所在团队总分是75）。

计划基于等价关系对构建双向图（如Player1<--->Player2<--->Player3<--->Player4），用统一ID标记同团队成员以汇总关联玩家分数，已设想如下C++接口：

void buildRelations(vector<pair<string, string>> equivalances) {
// 构建存储关系的数据结构：
// Player1<--->Player2<--->Player3<--->Player4 (team1)
// Player11<--->Player13 (team2)
}

int getTotalTeamScore(string player) {
// 传入Player1时，返回50+25=75，因为Player3属于Player1的团队
}

虽查阅相关资料，但仍不清楚如何设计存储关系的数据结构及检索关联玩家计算总分，恳请协助完成数据结构设计。

数据结构设计 #

采用**并查集（Union-Find）**搭配哈希表，这是处理等价类（团队归属）最高效的方案，比图遍历更适合批量合并和查询：

• unordered_map<string, string> parent：存储每个玩家的父节点，用于并查集的路径压缩与合并操作，最终同一团队的玩家会指向同一个根节点。
• unordered_map<string, int> scoreMap：存储每个玩家的分数，提前从分数对中初始化。
• unordered_map<string, int> teamTotalScore：存储每个团队根节点对应的总分，避免每次查询都遍历团队成员。

完整实现代码 #

#include <vector>
#include <unordered_map>
#include <string>

using namespace std;

class TeamScoreCalculator {
private:
    unordered_map<string, string> parent;
    unordered_map<string, int> scoreMap;
    unordered_map<string, int> teamTotalScore;

    // 并查集查找函数，带路径压缩
    string find(const string& player) {
        if (parent[player] != player) {
            parent[player] = find(parent[player]);
        }
        return parent[player];
    }

    // 并查集合并函数，同时更新团队总分
    void unite(const string& a, const string& b) {
        string rootA = find(a);
        string rootB = find(b);
        if (rootA != rootB) {
            // 将较小的树合并到较大的树下（可选，优化合并效率）
            parent[rootB] = rootA;
            // 合并两个团队的总分
            teamTotalScore[rootA] += teamTotalScore[rootB];
            // 删除被合并的根节点的总分记录
            teamTotalScore.erase(rootB);
        }
    }

public:
    // 初始化分数映射
    void initScores(const vector<pair<string, int>>& scores) {
        for (const auto& p : scores) {
            scoreMap[p.first] = p.second;
        }
    }

    void buildRelations(const vector<pair<string, string>>& equivalences) {
        // 初始化每个玩家的父节点为自身，同时初始化团队总分
        for (const auto& p : equivalences) {
            const string& player1 = p.first;
            const string& player2 = p.second;
            // 初始化player1的父节点和团队总分
            if (parent.find(player1) == parent.end()) {
                parent[player1] = player1;
                teamTotalScore[player1] = scoreMap.count(player1) ? scoreMap[player1] : 0;
            }
            // 初始化player2的父节点和团队总分
            if (parent.find(player2) == parent.end()) {
                parent[player2] = player2;
                teamTotalScore[player2] = scoreMap.count(player2) ? scoreMap[player2] : 0;
            }
            // 合并两个玩家所在的团队
            unite(player1, player2);
        }
    }

    int getTotalTeamScore(const string& player) {
        // 如果玩家不存在，返回0
        if (parent.find(player) == parent.end()) {
            return 0;
        }
        string root = find(player);
        return teamTotalScore[root];
    }
};

// 测试示例
int main() {
    TeamScoreCalculator calculator;
    // 初始化分数
    vector<pair<string, int>> scores = {{"Player1", 50}, {"Player3", 25}};
    calculator.initScores(scores);
    // 构建关系
    vector<pair<string, string>> equivalences = {{"Player1", "Player2"}, {"Player3", "Player4"}, {"Player2", "Player3"}, {"Player11", "Player13"}};
    calculator.buildRelations(equivalences);
    // 查询Player1的团队总分
    int total = calculator.getTotalTeamScore("Player1"); // 输出75
    return 0;
}

思路说明 #

1. 初始化阶段：initScores将所有玩家的分数存入scoreMap，方便后续初始化团队总分使用。
2. 构建关系阶段：
   • 遍历等价关系对，为每个首次出现的玩家初始化父节点为自身，并以其分数（无分数则为0）初始化团队总分。
   • 使用unite函数合并关联玩家的团队，合并时自动累加两个团队的总分，并更新父节点指向。
3. 查询总分阶段：
   • 通过find函数找到玩家所在团队的根节点（路径压缩优化查询效率）。
   • 直接返回根节点对应的团队总分，无需遍历所有团队成员。

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