重构一棵树的方案数

标签: 树 图

难度: Hard

给你一个数组 pairs ，其中 pairs[i] = [xi, yi] ，并且满足：

  • pairs 中没有重复元素
  • xi < yi

令 ways 为满足下面条件的有根树的方案数：

  • 树所包含的所有节点值都在 pairs 中。
  • 一个数对 [xi, yi] 出现在 pairs 中 当且仅当 xi 是 yi 的祖先或者 yi 是 xi 的祖先。
  • 注意：构造出来的树不一定是二叉树。

两棵树被视为不同的方案当存在至少一个节点在两棵树中有不同的父节点。

请你返回：

  • 如果 ways == 0 ，返回 0 。
  • 如果 ways == 1 ，返回 1 。
  • 如果 ways > 1 ，返回 2 。

一棵 有根树 指的是只有一个根节点的树，所有边都是从根往外的方向。

我们称从根到一个节点路径上的任意一个节点（除去节点本身）都是该节点的 祖先 。根节点没有祖先。

 

示例 1：

输入：pairs = [[1,2],[2,3]]
输出：1
解释：如上图所示，有且只有一个符合规定的有根树。

示例 2：

输入：pairs = [[1,2],[2,3],[1,3]]
输出：2
解释：有多个符合规定的有根树，其中三个如上图所示。

示例 3：

输入：pairs = [[1,2],[2,3],[2,4],[1,5]]
输出：0
解释：没有符合规定的有根树。

 

提示：

  • 1 <= pairs.length <= 105
  • 1 <= xi < yi <= 500
  • pairs 中的元素互不相同。

Submission

运行时间: 177 ms

内存: 44.2 MB

class Solution:
    def checkWays(self, pairs: List[List[int]]) -> int:
        # adj[x] 中存放所有与 x 有关系的节点，包括x自己
        adj = defaultdict(set)
        for x, y in pairs:
            adj[x].add(y)
            adj[y].add(x)
        # 对所有的节点，按照亲戚从多到少的顺序排序（定义亲戚是与x有关系的节点）
        vs = sorted(adj.keys(), key=lambda x:-len(adj[x]))

        if len(adj[vs[0]]) != len(vs) - 1:
            return 0

        multiAns = False
        for i, x in enumerate(vs):
            adj[x].add(x)
            # 每个节点x的 parent 是和x有关系且亲戚比x多的节点中，亲戚最少的节点。
            for y in reversed(vs[:i]):
                if x in adj[y]:
                    # 检测父亲的adj是否包含孩子的adj:
                    if adj[x].difference(adj[y]):
                        return 0
                    if len(adj[x]) == len(adj[y]):
                        multiAns = True
                    break
                    
        return multiAns + 1

        # 如何做到 O(n+m) 复杂度？不能去找每一个儿子的父亲，用父亲找儿子。
        # 记录每一个节点的最近的祖先，不断更新

Explain

该题解采用了图论的方法来解决问题。首先，将pairs中的每个数对看作无向图的边，构建邻接表adj，记录每个节点与之直接连接的节点。通过邻接表，可以判断任两个节点之间的直接关系。然后，将节点按照它们的连接数（度）从高到低排序。这一步是为了后续确定树的根节点，因为根节点在无向图中的连接数最多。接着，遍历每个节点，尝试将其作为子节点，寻找可能的父节点。父节点的条件是：必须与子节点直接相连，且父节点的度要高于子节点的度。如果找到符合条件的父节点，还需进一步检查，确保子节点的邻接节点都包含在父节点的邻接节点集中。如果在任何节点上发现不满足条件的情况，则返回0。如果存在多个节点可以有相同数量的连接，可能存在多种不同的树结构，设置标志multiAns为True。最后，根据是否存在多个解来返回1或2。

时间复杂度: O(n^2)

空间复杂度: O(n + m)

class Solution:
    def checkWays(self, pairs: List[List[int]]) -> int:
        adj = defaultdict(set) # 邻接表
        for x, y in pairs: # 构建无向图
            adj[x].add(y)
            adj[y].add(x)
        vs = sorted(adj.keys(), key=lambda x:-len(adj[x])) # 按连接数排序

        if len(adj[vs[0]]) != len(vs) - 1:
            return 0 # 检查是否有根节点

        multiAns = False
        for i, x in enumerate(vs):
            adj[x].add(x) # 包括自身以便检查包含关系
            for y in reversed(vs[:i]): # 寻找父节点
                if x in adj[y]:
                    if adj[x].difference(adj[y]):
                        return 0 # 父子关系不满足
                    if len(adj[x]) == len(adj[y]):
                        multiAns = True
                    break
        
        return multiAns + 1 # 根据是否有多个可能的树结构返回结果

Explore

在构建无向图时，将每个数对视为无向边是因为开始时我们不知道具体的父子关系，每对节点之间仅知道它们直接相连。使用无向边可以表示两个节点之间存在连接，而具体的方向（即谁是父节点，谁是子节点）将在之后的处理中根据节点的连接数和其他条件确定。这种处理方式并不矛盾，因为无向图只是一种中间步骤，用于表示节点间存在某种关系，最终的树结构仍将表现出清晰的祖先关系。

节点排序的目的是为了便于确定树的根节点。在树结构中，根节点通常是连接最多的节点，因为根节点直接或间接与树中所有其他节点相连。通过将节点按其连接数（度）从高到低排序，我们可以假设排序后列表中的第一个节点是根节点，因为它有最多的直接连接。这样的排序方法简化了根节点的识别过程，并为之后构建确切的父子关系提供了一个出发点。

在一棵树中，根节点应该与其他所有节点都有直接或间接的连接。如果一个节点作为根节点，其连接数即为它直接连接的节点数，那么这个数应该等于总节点数减一（即除去根节点自身的所有其他节点）。如果根节点的连接数不等于总节点数减一，这意味着至少有一个节点与根节点没有直接或间接的连接，从而违反了树结构的定义，其中任意两个节点都应该是连通的。因此，这种情况下一定不存在有效的树结构。

在树结构中，父节点和子节点之间存在层级关系，通常父节点会连接更多的节点，因为它不仅连接其子节点，还可能连接其他子节点或更多的分支。因此，如果一个节点作为另一个节点的父节点，它的连接数（度）通常会高于其子节点。这一条件帮助我们在构建树时维持正确的层级结构，确保每个节点都在适当的位置。如果违反这一条件，就可能出现逻辑上的矛盾，如一个子节点连接的节点数多于其父节点，这在正常的树结构中是不可能的。