Tideman问题lock_pairs函数异常：check50提示未正确锁定非循环对

核心问题分析 #

1. DFS函数的致命缺陷 #

• 缺少访问标记：当前DFS未记录已访问节点，遇到循环路径时会陷入无限递归，或重复遍历导致环判断错误。
• 检测方向完全错误：你调用dfs(pairs[i].winner, pairs[i].loser)是检查胜者能否到达败者，但实际需要检测的是败者能否回到胜者——添加winner→loser后，若败者能反向到达胜者，就会形成winner→loser→...→winner的环，这才是需要阻止的情况。

2. lock_pairs函数的逻辑错误 #

• 重复调用DFS：if和else分支重复执行相同的DFS检测，完全冗余。
• 错误的检测时机：你直接基于现有locked数组判断，没有临时添加当前边再检测，导致判断的是添加前的图状态，而非添加后的实际情况。
• 逻辑倒置：当前逻辑是"胜者到不了败者就锁定"，但正确逻辑是"添加边后不会形成环才锁定"。

修正后的代码 #

首先修复DFS函数，添加访问标记并调整检测逻辑：

#include <string.h> // 需要用到memset

bool visited[MAX_CANDIDATES]; // 假设MAX_CANDIDATES是你定义的候选人数组最大值

bool dfs(int start, int target) {
    if (start == target)
        return true;
    if (visited[start])
        return false;
    
    visited[start] = true;
    
    for (int i = 0; i < candidate_count; i++) {
        if (locked[start][i]) {
            if (dfs(i, target))
                return true;
        }
    }
    
    return false;
}

然后修复lock_pairs函数：

void lock_pairs(void) {
    for (int i = 0; i < pair_count; i++) {
        int winner = pairs[i].winner;
        int loser = pairs[i].loser;
        
        // 重置访问标记，确保每次DFS都是全新的遍历
        memset(visited, false, sizeof(visited));
        
        // 先临时锁定当前边，模拟添加后的状态
        locked[winner][loser] = true;
        // 检测败者能否回到胜者，若能则说明形成环，取消锁定
        if (dfs(loser, winner)) {
            locked[winner][loser] = false;
        }
        // 未形成环则保持锁定状态
    }
    return;
}

关键修正说明 #

• 访问标记：每次DFS前用memset重置visited数组，避免重复访问节点导致的无限递归或错误判断。
• 检测方向调整：改为检测loser到winner的路径，精准判断添加边后是否形成环。
• 临时边检测：先锁定边再检测，确保判断的是添加后的实际图状态，符合题目要求。
• 简化逻辑：去掉冗余的DFS调用，代码更高效简洁。

内容的提问来源于stack exchange，提问作者ROYAL GALAXY DRAGON