在C++中构造自反传递闭包以实现联赛选手排名

我需要为一个假想联赛的选手生成精确排名，将每个选手表示为图的节点，子节点代表被该选手直接击败的对手。核心需求是利用传递性推导未直接交手选手的关系（例如A击败B、B击败C，则可推导A击败C），最终输出每个选手的积分——即直接或间接击败的对手数量，格式为map<string, int>。

目前我用unordered_map<string, set<string>> graph存储图结构，key为选手名称，value是该选手直接击败的对手集合。但自己实现的传递闭包逻辑无法正常工作，代码如下：

// Apply the reflexive transitive closure to the graph
unordered_set<string> nodes;
for ( const auto &entry : graph ) {
    nodes.insert( entry.first );
}
for ( const auto &k : nodes ) {
    for ( const auto &i : nodes ) {
        for ( const auto &j : nodes ) {
            if ( graph[i].count( k ) == 1 && graph[k].count( j ) == 1 ) {
                graph[i].insert( j );
            }
        }
    }
}

// Check if the graph is strongly connected
for ( const auto &entry : graph ) {
    unordered_set<string> reachable;
    queue<string> node_queue;
    node_queue.push( entry.first );
    reachable.insert( entry.first );
    while ( !node_queue.empty() ) {
        string u = node_queue.front();
        node_queue.pop();
        for ( const auto &v : graph[u] ) {
            if ( !reachable.count( v ) ) {
                reachable.insert( v );
                node_queue.push( v );
            }
        }
    }
    if ( reachable.size() != graph.size() ) {
        return false;
    }
}

return true;

改进方案与实现建议 #

1. 修复传递闭包的实现问题 #

你当前的三重循环只执行一轮，无法处理多层传递的情况（比如A→B→C→D，一轮循环只能得到A→C，无法推导A→D）。可以采用两种可靠的实现方式：

方式一：Floyd-Warshall算法（迭代至收敛）

重复执行三重循环，直到没有新的边可以添加到图中：

unordered_set<string> nodes;
for (const auto& entry : graph) {
    nodes.insert(entry.first);
}

bool updated;
do {
    updated = false;
    for (const auto& k : nodes) {
        for (const auto& i : nodes) {
            for (const auto& j : nodes) {
                // 若i能到k，k能到j，且i尚未能到j，则添加i→j的边
                if (graph[i].count(k) && graph[k].count(j) && !graph[i].count(j)) {
                    graph[i].insert(j);
                    updated = true;
                }
            }
        }
    }
} while (updated);

方式二：BFS/DFS计算单个节点的所有可达节点（更高效）

对每个节点单独做BFS或DFS，直接遍历出所有能到达的节点（即被该选手直接或间接击败的对手），同时可以直接统计积分：

// 存储每个节点的所有可达对手（不含自身）
unordered_map<string, unordered_set<string>> all_defeated;

for (const auto& entry : graph) {
    const string& player = entry.first;
    queue<string> q;
    unordered_set<string> visited;

    q.push(player);
    visited.insert(player);

    while (!q.empty()) {
        string current = q.front();
        q.pop();

        for (const string& opponent : graph[current]) {
            if (!visited.count(opponent)) {
                visited.insert(opponent);
                q.push(opponent);
                // 可选：同步更新原graph的传递闭包
                graph[player].insert(opponent);
            }
        }
    }

    // 移除自身，剩下的就是所有被击败的对手
    visited.erase(player);
    all_defeated[player] = visited;
}

// 生成最终排名积分
map<string, int> ranking;
for (const auto& pair : all_defeated) {
    ranking[pair.first] = pair.second.size();
}

这种方法的时间复杂度为O(N*(N+E))，比Floyd-Warshall的O(N³)更高效，尤其适用于边数较少的场景。

2. 优化强连通性检查 #

你当前对每个节点都做一次BFS，效率较低。可以通过正向+反向图的BFS来优化：

bool isStronglyConnected(const unordered_map<string, set<string>>& graph) {
    if (graph.empty()) return true;

    // 构建反向图：key是被击败者，value是击败自己的选手
    unordered_map<string, set<string>> reverse_graph;
    for (const auto& entry : graph) {
        const string& winner = entry.first;
        for (const string& loser : entry.second) {
            reverse_graph[loser].insert(winner);
        }
        // 确保所有节点都在反向图中存在
        if (!reverse_graph.count(winner)) {
            reverse_graph[winner] = {};
        }
    }

    // 选第一个节点做正向BFS，检查是否能到达所有节点
    string start = graph.begin()->first;
    unordered_set<string> forward_reachable;
    queue<string> q;
    q.push(start);
    forward_reachable.insert(start);

    while (!q.empty()) {
        string u = q.front();
        q.pop();
        for (const string& v : graph.at(u)) {
            if (!forward_reachable.count(v)) {
                forward_reachable.insert(v);
                q.push(v);
            }
        }
    }
    if (forward_reachable.size() != graph.size()) return false;

    // 对反向图做BFS，检查是否所有节点能到达起始节点
    unordered_set<string> reverse_reachable;
    q.push(start);
    reverse_reachable.insert(start);

    while (!q.empty()) {
        string u = q.front();
        q.pop();
        for (const string& v : reverse_graph.at(u)) {
            if (!reverse_reachable.count(v)) {
                reverse_reachable.insert(v);
                q.push(v);
            }
        }
    }

    return reverse_reachable.size() == graph.size();
}

3. 关键注意事项 #

• 积分计算必须排除选手自身，因为击败自己没有意义
• 如果图中存在循环胜负（比如A击败B、B击败C、C击败A），则这些选手会互相计入积分，此时无法生成严格的全序排名，只能按积分排序
• 若仅需要积分而不需要保留完整的传递闭包图，可以跳过更新原graph的步骤，直接用BFS/DFS统计可达节点数量即可

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