题目概述

有一个国家 K，它有 N 个城市和 M 条道路连接这些城市。现在需要通过交换道路两端城市的编号来使得任意一条简单路径上的城市编号按升序或降序排列。请计算达到这个目标所需的最小操作次数（即需要多少天）。

函数签名如下：

def best_swap(N: int, M: int, E: List[List[int]]) -> int:
    pass

解题思路

首先，可以明确以下几点：

• 每个道路都连接了两个不同的城市。
• 没有两条道路在非城市地点相交。

观察数据后可以发现：如果 K 国包含一个由道路直接连成的线段，那么无论如何交换这些城市的编号，都无法满足要求。因此，在这种情况下，答案是 -1。否则，答案是 0，因为 K 国已经处于“良好”的状态。

我们可以尝试一个暴力的解法来处理规模较小的问题，但是对于规模较大的问题，时间复杂度会非常高。因此，我们需要找到更优的解法。

我们可以通过建立图的方式来理解问题。其中，每个城市是图中的一个节点，每条道路是节点之间的边。根据题意，我们需要通过一系列节点交换操作，将图变为一个序列。由于节点只能通过边进行移动，我们的目标是找到一个序列，使得任意路径上的节点编号都是单调递增或单调递减的。

要解决这个问题，我们需要考虑以下两种情况：

• 如果图是一个连续的线段（即所有节点都通过单个边连接），那么无论如何交换节点的编号，我们都无法满足要求。在这种情况下，答案是 -1。
• 否则，我们可以将图中的每个环（即由多个边组成的路径）都按升序或降序重新编号。

因此，我们可以计算出图中有多少个环，然后将这些环中的节点按升序或降序重新编号。这样一来，我们就构造了一个满足要求的图，并且进行这些操作所需的天数也达到了最小值。

时间复杂度分析

我们需要遍历每个节点，以及它们的边。因此，时间复杂度为 O(N+M)。

算法实现

from typing import List

def best_swap(N: int, M: int, E: List[List[int]]) -> int:
    # 构建环的集合
    loops = []
    visited = [False] * N
    for i in range(N):
        # 如果节点未访问过，则进行 DFS
        if not visited[i]:
            loop = set()
            dfs(i, -1, E, visited, loop)
            loops.append(loop)

    # 判断是否有连续线段
    if len(loops) == 1 and len(E) == N - 1:
        return -1

    # 计算操作次数
    count = 0
    for loop in loops:
        sorted_loop = sorted(loop)
        if loop != sorted_loop and loop != sorted_loop[::-1]:
            count += 1

    return count


def dfs(node: int, parent: int, E: List[List[int]], visited: List[bool], loop: set):
    visited[node] = True
    loop.add(node)
    for edge in E:
        if node in edge:
            next_node = edge[1] if edge[0] == node else edge[0]
            if next_node != parent and not visited[next_node]:
                dfs(next_node, node, E, visited, loop)