合法重新排列数对

标签: 深度优先搜索 图 欧拉回路

难度: Hard

给你一个下标从 0 开始的二维整数数组 pairs ，其中 pairs[i] = [starti, endi] 。如果 pairs 的一个重新排列，满足对每一个下标 i （ 1 <= i < pairs.length ）都有 endi-1 == starti ，那么我们就认为这个重新排列是 pairs 的一个 合法重新排列 。

请你返回 任意一个 pairs 的合法重新排列。

注意：数据保证至少存在一个 pairs 的合法重新排列。

示例 1：

输入：pairs = [[5,1],[4,5],[11,9],[9,4]]
输出：[[11,9],[9,4],[4,5],[5,1]]
解释：
输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti 。
end0 = 9 == 9 = start1 
end1 = 4 == 4 = start2
end2 = 5 == 5 = start3

示例 2：

输入：pairs = [[1,3],[3,2],[2,1]]
输出：[[1,3],[3,2],[2,1]]
解释：
输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti 。
end0 = 3 == 3 = start1
end1 = 2 == 2 = start2
重新排列后的数组 [[2,1],[1,3],[3,2]] 和 [[3,2],[2,1],[1,3]] 都是合法的。

示例 3：

输入：pairs = [[1,2],[1,3],[2,1]]
输出：[[1,2],[2,1],[1,3]]
解释：
输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti 。
end0 = 2 == 2 = start1
end1 = 1 == 1 = start2

提示：

  • 1 <= pairs.length <= 105
  • pairs[i].length == 2
  • 0 <= starti, endi <= 109
  • starti != endi
  • pairs 中不存在一模一样的数对。
  • 至少 存在 一个合法的 pairs 重新排列。

Submission

运行时间: 452 ms

内存: 79.0 MB

class Solution:
    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
        g = defaultdict(list)
        indeg = defaultdict(int)
        for u,v in pairs:
            g[u].append(v)
            indeg[v] += 1
        start = pairs[0][0]
        for k,v in g.items():
            if len(v) > indeg[k]:
                start = k 
                break 
        # print(g[start],indeg[start],start)
        ans = []
        def dfs(u):
            # print(u)
            while g[u]:
                v = g[u].pop()
                dfs(v)
                ans.append((u,v))
        dfs(start)
        return ans[::-1]

Explain

题解利用了图的深度优先搜索（DFS）来找到一条合法的路径，使得每对数的第二个元素正好是下一对数的第一个元素。首先，构建一个图g，其中每个节点代表数对中的starti，每个节点指向endi。同时，计算每个节点的入度（indeg）。在选择起始点时，寻找一个节点的出度大于入度的节点作为起始节点（如果存在这样的节点，则意味着这是唯一的起点，否则任意节点均可）。然后从起始点开始使用DFS，每次访问一个节点并在访问后将其从图中删除，确保每个连接只被使用一次。访问的顺序被反转存储在结果数组中，因为DFS会首先到达深层节点，而我们需要的顺序是从起点开始的顺序。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
        g = defaultdict(list)
        indeg = defaultdict(int)
        for u,v in pairs:
            g[u].append(v)
            indeg[v] += 1
        start = pairs[0][0]
        for k,v in g.items():
            if len(v) > indeg[k]:
                start = k 
                break 
        ans = []
        def dfs(u):
            while g[u]:
                v = g[u].pop()
                dfs(v)
                ans.append((u,v))
        dfs(start)
        return ans[::-1]  # 将结果反转以获得正确的顺序

Explore

在一个有效的重新排列问题中，理论上不会出现存在多个节点出度大于入度的情况，因为这将违反每对数的第二个元素正好是下一对数的第一个元素的规则。如果一个图中的节点出现出度大于入度的情况超过一个，则无法形成一个连续的路径。但是，如果确实发现多个这样的节点，在算法逻辑中通常会视为数据输入错误或者问题描述的特殊情况，需要额外的错误检查或特殊处理。

在DFS过程中，每次递归访问一个节点（从当前节点到下一个节点），我们会在DFS返回后将当前的数对添加到结果数组中。因此，最深的递归调用（最远的节点对）最先被添加到结果数组。这意味着结果数组中数对的顺序是从终点到起点的顺序。为了得到一个从起点到终点的路径，我们需要将数组反转，这样才能正确地按照题目要求输出从起始点开始的路径顺序。

在构建图时使用`defaultdict`可以简化代码，因为如果使用普通字典，在添加节点和边时需要先检查键是否存在，如果不存在则首先创建一个空列表。使用`defaultdict`，如果键不存在，它会自动为该键提供一个默认的空列表，从而避免了额外的键存在性检查，使得代码更简洁、更易于管理。

在此题解中，每次访问一个节点时，会从图中删除这个节点到其它节点的连接（使用`pop`操作）。这种方法确保了每个连接只被访问一次。因此，虽然DFS过程中可能会多次到达同一个节点，但每次到达时可用的连接都是不同的。这里没有显式的检查节点是否被访问过的机制，而是通过确保每个连接只使用一次来防止重复访问同一个路径。