依赖关系检测与版本更新

题目描述

爱丽丝在人偶制作过程中需要管理部件之间的依赖关系。每组数据包含若干条依赖关系，每条表示“人偶 u 依赖于部件 v，要求的版本号为 version”。

需要完成两件事：

1. 检测依赖关系中是否存在循环依赖（有向图中的环）
2. 如果无环，对于每个被依赖的部件 v，找出所有依赖于它的条目中的最大版本号，并按输入顺序输出更新后的依赖关系

数据范围：

• 编号 u, v 为正整数，且 1 ≤ u, v ≤ 10⁹
• 版本号 1 ≤ version ≤ 99
• 在同一组数据中，同一个依赖序对 (u, v) 最多出现一次
• 依赖关系数量 0 < n < 100

示例

输入：

3
1,2,23
2,3,34
4,2,25
3
1,2,23
2,3,34
3,1,12

输出：

1,2,25
2,3,34
4,2,25
false

说明：

第一组：人偶 1 依赖 2（版本 23），人偶 4 也依赖 2（版本 25），因此部件 2 的最大需求版本为 25；人偶 2 依赖 3（版本 34），因此部件 3 的最大需求版本为 34。网络中不存在环。

第二组：1 依赖 2，2 依赖 3，3 依赖 1，构成闭环，输出 false。

解题思路

题目分为两个子问题：

1. 检测有向图环

方法一：拓扑排序（Kahn 算法）

• 统计每个节点的入度
• 将所有入度为 0 的节点入队
• 每次出队一个节点，将其所有邻居的入度减 1，若邻居入度变 0 则入队
• 最终：处理的节点数 < 总节点数 → 有环

方法二：DFS 三色标记法

• 白色（0）：未访问
• 灰色（1）：正在访问中（在递归栈中）
• 黑色（2）：已完成访问
• DFS 时遇到灰色节点即发现环

2. 更新版本号

遍历所有依赖关系，记录每个被依赖节点 v 的最大版本号；然后按输入顺序用最大值替换原版本号。

代码实现

/**
 * 拓扑排序（Kahn 算法）检测有向图是否有环
 * 时间复杂度：O(V + E)
 */
function isLoop(list) {
    const indegree = {};
    const graph = {};

    for (const [u, v] of list) {
        if (!(u in indegree)) indegree[u] = 0;
        if (!(v in indegree)) indegree[v] = 0;
        if (!graph[u]) graph[u] = [];
        if (!graph[v]) graph[v] = [];
    }

    for (const [u, v] of list) {
        graph[v].push(u);           // v 指向 u（被依赖者 → 依赖者）
        indegree[u] = (indegree[u] || 0) + 1;
    }

    const queue = [];
    const allNodes = Object.keys(indegree);
    for (const node of allNodes) {
        if (indegree[node] === 0) queue.push(node);
    }

    let processed = 0;
    while (queue.length > 0) {
        const u = queue.shift();
        processed++;
        for (const next of graph[u] || []) {
            indegree[next]--;
            if (indegree[next] === 0) queue.push(next);
        }
    }

    return processed < allNodes.length;
}

/**
 * DFS 三色标记法检测有向图是否有环
 * 时间复杂度：O(V + E)，空间复杂度：O(V)
 */
function isLoopDFS(list) {
    const graph = {};
    const color = {}; // 0=白 1=灰 2=黑

    for (const [u, v] of list) {
        if (!graph[v]) graph[v] = [];
        graph[v].push(u);
        color[u] = 0;
        color[v] = 0;
    }

    function dfs(node) {
        color[node] = 1;
        for (const next of graph[node] || []) {
            if (color[next] === 1) return true;  // 遇到灰色 → 有环
            if (color[next] === 0 && dfs(next)) return true;
        }
        color[node] = 2;
        return false;
    }

    for (const node of Object.keys(color)) {
        if (color[node] === 0 && dfs(node)) return true;
    }
    return false;
}

/**
 * 更新版本号：对每个被依赖节点 v，取所有入边的最大 version
 */
function getFixedlist(list) {
    const maxVersionMap = {};
    for (const [main, pre, version] of list) {
        maxVersionMap[pre] = Math.max(version, maxVersionMap[pre] || 0);
    }
    return list.map(([main, pre]) => [main, pre, maxVersionMap[pre]]);
}

复杂度分析

• 时间复杂度： O(V + E)，建图和拓扑排序/DFS 都是线性时间。n < 100，非常快。
• 空间复杂度： O(V + E)，存储邻接表和入度表。

3
1,2,23
2,3,34
4,2,25
3
1,2,23
2,3,34
3,1,12

1,2,25
2,3,34
4,2,25
false