可以到达所有点的最少点数目

标签: 图

难度: Medium

给你一个 有向无环图 ， n 个节点编号为 0 到 n-1 ，以及一个边数组 edges ，其中 edges[i] = [fromi, toi] 表示一条从点  fromi 到点 toi 的有向边。

找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。

你可以以任意顺序返回这些节点编号。

示例 1：

输入：n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
输出：[0,3]
解释：从单个节点出发无法到达所有节点。从 0 出发我们可以到达 [0,1,2,5] 。从 3 出发我们可以到达 [3,4,2,5] 。所以我们输出 [0,3] 。

示例 2：

输入：n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
输出：[0,2,3]
解释：注意到节点 0，3 和 2 无法从其他节点到达，所以我们必须将它们包含在结果点集中，这些点都能到达节点 1 和 4 。

提示：

  • 2 <= n <= 10^5
  • 1 <= edges.length <= min(10^5, n * (n - 1) / 2)
  • edges[i].length == 2
  • 0 <= fromi, toi < n
  • 所有点对 (fromi, toi) 互不相同。

Submission

运行时间: 73 ms

内存: 41.4 MB

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        in_deg = [0] * n
        for _, x in edges: in_deg[x] += 1
        return [i for i, d in enumerate(in_deg) if not d]

Explain

该题目要求找到最少的点集，使得从这些点出发可以到达图中的所有节点。在有向无环图中，可以直接利用入度的概念来解决。入度为零的节点没有其他节点指向它，因此这些节点必须被包含在答案中，以确保从这些点出发可以访问到所有其他可达的节点。算法首先初始化一个记录每个节点入度的数组，然后遍历所有边，对每条边的终点节点的入度加一。最后，遍历入度数组，将入度为零的节点加入结果列表，这些就是所求的最小点集。

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

空间复杂度: O(n)

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        in_deg = [0] * n  # 初始化入度数组
        for _, x in edges: in_deg[x] += 1  # 计算每个节点的入度
        return [i for i, d in enumerate(in_deg) if not d]  # 返回入度为零的所有节点

Explore

在有向图中，入度为零的节点表示没有其他节点指向这个节点。因此，任何从其他节点出发的路径都无法到达入度为零的节点。为了确保能访问到所有节点，入度为零的节点必须被直接选择作为起始点。从这些起始点出发，我们可以访问到它们可以到达的所有节点。因此，选择所有入度为零的节点可以保证覆盖到所有的节点或者从这些节点可以通过路径访问到的节点。

如果图中存在孤立节点，由于这些节点既没有入边也没有出边，它们的入度也会是零。因此，这种算法会把孤立节点也包含在返回的结果中，因为它们也需要被作为起始点才能被访问到。这样可以确保所有节点都被覆盖。

在当前算法实现中，自环会增加该节点的入度。因为算法简单地统计了每个节点作为边的终点的次数，包括自己指向自己的情况。这意味着如果一个节点有自环，它的入度至少为1，使其不会被选为起始点。然而，从解决问题的角度看，自环不影响从其他节点到达这个节点的能力，因此在这种情况下，自环对问题的解决没有负面影响。

题目描述中提供了节点总数n，和一个从0到n-1的节点编号范围。这意味着节点编号是连续的，从0到n-1。因此，我们可以安全地使用一个大小为n的数组来初始化每个节点的入度，每个索引对应一个节点编号。如果节点编号不是连续的，我们需要额外的数据结构，如字典，来处理不连续的或非整数的节点编号。