最长交错路径（Longest Alternating Path in a Directed Graph）

题目描述

给你一个有向图，图中有 n 个节点，节点编号从 0 到 n-1。同时给你一个整数数组 values，其中 values[i] 表示节点 i 的值。图中还有 m 条有向边，每条边从节点 u 指向节点 v。

我们定义一个路径为“交错路径”，如果路径上相邻节点的值交替严格递增和严格递减。更形式化地，对于一个节点序列 p0, p1, ..., pk，对于所有满足 0 ≤ i < k 的 i，必须满足以下条件之一：

• 如果 i 是偶数，则 values[p_i] < values[p_(i+1)]（递增）。
• 如果 i 是奇数，则 values[p_i] > values[p_(i+1)]（递减）。
  或者反过来：
• 如果 i 是偶数，则 values[p_i] > values[p_(i+1)]（递减）。
• 如果 i 是奇数，则 values[p_i] < values[p_(i+1)]（递增）。

换句话说，路径上节点值的比较符号是交替的（<, >, <, >, ... 或 >, <, >, <, ...）。路径的长度定义为路径上边的数量（即节点数减1）。单节点路径长度为0，也视为交错路径。

你的任务是：找到图中最长交错路径的长度。注意路径不一定是简单路径，可以有环吗？通常我们要求路径是简单路径（无重复节点），但本题目通常限定为简单路径（无环）。我们假设图是有向无环图（DAG），这样我们可以用动态规划按拓扑顺序求解。如果图中可能有环，则问题会变得更复杂（需要处理环）。为了简化，我们先考虑有向无环图（DAG）的情况。

输入：

• 整数 n，表示节点数。
• 数组 values，长度为 n，values[i] 表示节点 i 的值。
• 整数 m，表示边数。
• 接下来 m 行，每行两个整数 u, v，表示一条从 u 到 v 的有向边。保证图中无环（DAG）。

输出：一个整数，表示最长交错路径的长度。

示例：

n = 4
values = [1, 2, 3, 4]
边：0->1, 1->2, 2->3

解释：所有节点值严格递增。如果路径必须以交替方式，那么最长交错路径是单个节点（长度为0）。比如路径 0->1 是递增的，但接下来如果走 1->2 又是递增，不满足交替（我们需要递增后紧跟递减，或者递减后紧跟递增）。所以最长路径可能是 0->1（长度1，但这是单一的递增，不符合交替？实际上，单条边路径（长度为1）总是满足交替吗？对于长度为1的路径，它只有一个比较，可以是任意比较，所以总是满足交替条件。所以长度为1的路径是合法的。但我们需要更长的路径。在此例中，由于所有值递增，任何长度为2的路径（两条边）都无法同时满足递增和递减交替。例如 0->1->2：0->1 是递增，1->2 也是递增，第二个比较不是递减，所以不合法。所以最长交错路径长度为1。

另一个例子：

n = 5
values = [5, 3, 4, 2, 1]
边：0->1, 1->2, 2->3, 3->4, 0->2, 1->3, 2->4]

一个可能的最长交错路径：0->1 (5>3 递减), 1->2 (3<4 递增), 2->3 (4>2 递减), 3->4 (2>1 递减) 但这里 2->3 递减，3->4 也递减，不交替。实际上，如果我们取 0->1 (递减), 1->2 (递增), 2->3 (递减) 长度3，是合法的。所以答案是3。

解题目标：在DAG中，找到满足值交替大小关系的最长路径长度。

解题思路

这是一个基于图的动态规划问题。由于图是无环的，我们可以按照拓扑顺序处理节点。对于每个节点，我们需要考虑以该节点为终点的最长交错路径。但由于交替规则，我们需要知道当前路径的最后一步是比较方向（是递增还是递减），才能决定下一步可以接什么样的边。

状态定义：
定义两个状态数组：

• inc[i]：表示以节点 i 为路径最后一个节点，且最后一步比较是递增（即从某个节点 j 到 i 满足 values[j] < values[i]）的情况下，从某个起点到 i 的最长交错路径长度。
• dec[i]：表示以节点 i 为路径最后一个节点，且最后一步比较是递减（即从某个节点 j 到 i 满足 values[j] > values[i]）的情况下，从某个起点到 i 的最长交错路径长度。

注意：这里“最后一步比较”指的是到达 i 的那条边上的比较。对于 inc[i]，意味着到达 i 之前的那一步是递增（即前驱节点的值小于 i 的值）。对于 dec[i]，意味着到达 i 之前的那一步是递减（前驱节点的值大于 i 的值）。

转移方程：
我们考虑所有指向节点 i 的入边 (j, i)。根据边上的值比较关系，更新 inc[i] 和 dec[i]。

• 如果 values[j] < values[i]（递增边）：
  那么从 j 到 i 是递增。如果我们想要以 i 结尾且最后一步是递增的路径，那么这条路径的前一步（以 j 结尾）的最后一步应该是递减（因为我们需要交替：递减后接递增）。所以我们可以用 dec[j] 来更新 inc[i]。
  转移：inc[i] = max(inc[i], dec[j] + 1)。
• 如果 values[j] > values[i]（递减边）：
  那么从 j 到 i 是递减。类似地，如果我们想要以 i 结尾且最后一步是递减的路径，那么前一步应该是以 j 结尾且最后一步是递增的路径。所以用 inc[j] 来更新 dec[i]。
  转移：dec[i] = max(dec[i], inc[j] + 1)。

初始化：对于每个节点 i，inc[i] = 0, dec[i] = 0。因为单个节点路径长度为0，且没有最后一步比较方向，但我们可以认为 inc 和 dec 都至少为0。实际上，单个节点路径没有边，所以没有比较方向。但为了方便，我们初始化 inc 和 dec 为0，表示从该节点开始（或结束）的路径长度为0。当我们处理边时，会加上1。

计算顺序：
由于图是DAG，我们可以先进行拓扑排序，然后按照拓扑顺序依次处理每个节点 i。对于每个节点 i，我们遍历其所有入边（即所有前驱 j），根据上述规则更新 inc[i] 和 dec[i]。因为拓扑排序保证处理 i 时，其所有前驱 j 已经被处理过了（即 inc[j] 和 dec[j] 已经计算好了）。

最终答案：
遍历所有节点 i，取 max(inc[i], dec[i]) 的最大值，即为最长交错路径的长度。

注意：路径长度是边的数量。我们初始化 inc 和 dec 为0，表示路径长度为0（单个节点）。当从 j 扩展到 i 时，路径长度增加1（即边 j->i）。所以转移方程中 +1 是正确的。

边界情况：

• 如果图中没有边，则每个节点都是孤立点，最长路径长度为0。
• 如果所有边都满足同一种比较（全递增或全递减），则最长交错路径长度为1（因为只有一条边的路径总是合法，两条边就需要交替，而全同向无法交替，所以长度最多为1）。

复杂度：

• 拓扑排序 O(n + m)。
• 动态规划过程：对于每条边，我们进行常数次更新。总时间复杂度 O(n + m)。空间复杂度 O(n)。

逐步推导

我们用一个具体例子来演示。

假设：
n = 6
values = [5, 2, 4, 3, 1, 6]
边：
0->1 (5>2 递减)
0->2 (5>4 递减)
1->3 (2<3 递增)
2->3 (4>3 递减)
2->4 (4>1 递减)
3->5 (3<6 递增)
4->5 (1<6 递增)

图结构如下（箭头表示有向边，旁边标注比较关系）：

节点0 (5)
  ↘ 递减
   节点1 (2) → 递增 → 节点3 (3) → 递增 → 节点5 (6)
  ↘ 递减                     ↗
   节点2 (4) → 递减 → 节点4 (1) → 递增 → 节点5
        ↘ 递减 ↘
          节点3  节点4

注意：0->2 递减，2->3 递减，2->4 递减，等等。

我们需要计算最长交错路径。

步骤1：拓扑排序
这个图是DAG，一种拓扑顺序可以是 [0,1,2,3,4,5]（实际上可能有多种，但0入度为0，之后1和2入度来自0，3入度来自1和2，4入度来自2，5入度来自3和4）。我们按此顺序处理。

初始化：
inc = [0,0,0,0,0,0]
dec = [0,0,0,0,0,0]

步骤2：按拓扑顺序处理每个节点

• 节点0：没有入边，所以 inc[0] 和 dec[0] 保持0。

• 节点1：入边 0->1 (5>2 递减)。
  比较：values[0]=5 > values[1]=2，是递减边。
  因此，我们可以用 inc[0] 来更新 dec[1]。
  dec[1] = max(dec[1], inc[0]+1) = max(0, 0+1) = 1。
  inc[1] 保持不变（因为没有递增入边）。
  现在 inc[1]=0, dec[1]=1。

• 节点2：入边 0->2 (5>4 递减)。
  递减边，用 inc[0] 更新 dec[2]。
  dec[2] = max(0, inc[0]+1) = 1。
  inc[2]=0。

• 节点3：有两条入边：

  1. 边 1->3: values[1]=2 < values[3]=3，递增边。
     对于递增边，我们用 dec[1] 更新 inc[3]。
     inc[3] = max(inc[3], dec[1]+1) = max(0, 1+1) = 2。
  2. 边 2->3: values[2]=4 > values[3]=3，递减边。
     对于递减边，我们用 inc[2] 更新 dec[3]。
     dec[3] = max(dec[3], inc[2]+1) = max(0, 0+1) = 1。
     所以 inc[3]=2, dec[3]=1。

• 节点4：入边 2->4: values[2]=4 > values[4]=1，递减边。
  用 inc[2] 更新 dec[4]。
  dec[4] = max(0, inc[2]+1) = 1。
  inc[4]=0。

• 节点5：有两条入边：

  1. 边 3->5: values[3]=3 < values[5]=6，递增边。
     用 dec[3] 更新 inc[5]。
     inc[5] = max(inc[5], dec[3]+1) = max(0, 1+1) = 2。
  2. 边 4->5: values[4]=1 < values[5]=6，递增边。
     用 dec[4] 更新 inc[5]。
     inc[5] = max(inc[5], dec[4]+1) = max(2, 1+1) = 2。（相等，还是2）
     没有递减入边，所以 dec[5]=0。

步骤3：计算答案
对于每个节点，取 inc 和 dec 的最大值：
节点0: max(0,0)=0
节点1: max(0,1)=1
节点2: max(0,1)=1
节点3: max(2,1)=2
节点4: max(0,1)=1
节点5: max(2,0)=2
所以最大值是2，即最长交错路径长度为2。

验证：我们可以找到长度为2的路径，例如 0->1 (递减), 1->3 (递增) 长度2。还有 0->2 (递减), 2->3 (递减) 不交替，不行。还有 2->3 (递减), 3->5 (递增) 长度2。所以答案为2。

思考：如果路径可以更长，比如 0->1 (递减), 1->3 (递增), 3->5 (递增) 最后两步都是递增，不交替。所以最长就是2。

扩展讨论

如果图中有环怎么办？此时无法进行拓扑排序，因为存在循环依赖。但交错路径要求简单路径（无重复节点），所以不能包含环。我们可以考虑在一般有向图中找最长简单路径，但这是NP难的（因为最长路径问题是NP难的）。所以通常题目会限定为DAG，或者要求路径是简单的但图是任意有向图，此时可能需要用记忆化搜索+状态压缩（节点数少时）或使用DFS+记忆化。

对于有向图（可能有环），但要求简单路径，我们可以用记忆化搜索，状态为 (当前节点, 上一步比较方向)，用DFS遍历所有简单路径，但最坏情况是指数复杂度。如果节点数n较小（比如n≤20），可以用状态压缩DP。

代码实现（伪代码）

function longestAlternatingPath(n, values, edges):
    # 建图，邻接表存储出边，同时为了方便，我们也存储入边或直接遍历边列表
    # 由于需要按照拓扑顺序，我们先计算每个节点的入度，进行拓扑排序
    indeg = [0]*n
    adj = [[] for _ in range(n)]  # 出边列表
    for (u,v) in edges:
        adj[u].append(v)
        indeg[v] += 1
    
    # 拓扑排序
    from collections import deque
    q = deque()
    for i in range(n):
        if indeg[i] == 0:
            q.append(i)
    topo = []
    while q:
        u = q.popleft()
        topo.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    # 如果图中存在环，拓扑排序后 topo 长度小于 n，但题目保证无环，所以略过处理

    inc = [0]*n
    dec = [0]*n
    ans = 0
    # 按照拓扑顺序处理节点
    for u in topo:
        # 遍历所有入边，我们需要存储入边列表，或者直接遍历所有边
        # 为了效率，可以预先存储入边列表
        # 这里为了简单，我们遍历所有边，检查终点是否为 u
        # 实际实现时可以建立反向邻接表
    # 更高效的做法：在构建图时同时构建反向邻接表 rev_adj
    rev_adj = [[] for _ in range(n)]
    for (u,v) in edges:
        rev_adj[v].append(u)  # 存储进入 v 的边
    
    for u in topo:
        for prev in rev_adj[u]:
            if values[prev] < values[u]:  # 递增边
                inc[u] = max(inc[u], dec[prev] + 1)
            elif values[prev] > values[u]:  # 递减边
                dec[u] = max(dec[u], inc[prev] + 1)
        ans = max(ans, inc[u], dec[u])
    return ans

总结：本题的核心是将路径的交替性质用两个状态表示，然后利用DAG的拓扑顺序进行动态规划。状态转移依赖于前驱节点和值的大小关系。最终取所有状态的最大值作为答案。