NeetCode刷题第17天(2025.1.27)

086 Course Schedule II 课程安排二

您将获得一个数组 prerequisites ，其中 prerequisites[i] = [a, b] 表示如果您想学习课程 a ，则必须先学习课程 b 。

• 例如， [0, 1] 对表示要学习课程 0 ，您必须首先学习课程 1 。

您总共需要学习 numCourses 门课程，标记为 0 到 numCourses - 1 。
返回您可以完成所有课程的有效课程顺序。如果有很多有效答案，则返回其中任何一个。如果无法完成所有课程，则返回空数组。

示例1：
Input: numCourses = 3, prerequisites = [[1,0]]
Output: [0,1,2]
说明：我们必须确保课程 0 在课程 1 之前学习。示例2：
Input: numCourses = 3, prerequisites = [[0,1],[1,2],[2,0]]
Output: []
说明：不可能完成所有课程。

解题1： 循环检测（DFS）

class Solution:def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:prereq = {c:[] for c in range(numCourses)}for crs, pre in prerequisites:prereq[crs].append(pre)# 1个课程有3个可能的状态# visited -> crs  has been added to output# visiting -> crs not added to output, but added to cycle# unvisited -> crs not added to output or cycleoutput = []visit, cycle = set(), set()def dfs(crs):if crs in cycle:return Falseif crs in visit:return Truecycle.add(crs)for pre in prereq[crs]:if dfs(pre) == False:return Falsecycle.remove(crs)visit.add(crs)output.append(crs)return Truefor c in range(numCourses):if dfs(c) == False:return []return output

时间复杂度: O$(V+E)$
空间复杂度: $O(V+E)$
V 是顶点数，E 是边的数量。

087 Graph Valid Tree 图有效树

给定从 0 到 n - 1 标记的 n 节点和无向边列表（每条边是一对节点），编写一个函数来检查这些边是否组成一棵有效的树。

示例1：
Input: n = 5,  edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Output: true示例2：
Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output: false

解题1： 循环检测（DFS）

首先使用深度优先遍历，并把每次遍历到的节点放入visited中，遍历完后如果visited的个数等于总的节点个数，那么说明他们都是联通的。

此外，我们还要保证不存在循环。所以我们会为每个节点记录一个prev来表示他的父节点，以防止错误判断存在循环。

class Solution:def validTree(self, n: int, edges: List[List[int]]) -> bool:if not n:return Trueadj = {i:[] for i in range(n)}for n1, n2 in edges:adj[n1].append(n2)adj[n2].append(n1)visit = set()def dfs(i, prev):if i in visit:return Falsevisit.add(i)for j in adj[i]:if j == prev:continueif not dfs(j, i):return Falsereturn Truereturn dfs(0, -1) and n == len(visit)

时间复杂度: O$(V+E)$
空间复杂度: $O(V+E)$
V 是顶点数，E 是边的数量。

088 Number of Connected Components in an Undirected Graph 无向图中的连接组件数量

有一个带有n节点的无向​​图。还有一个edges阵列，其中edges[i] = [a, b]表示图表中的节点a和节点b之间存在边缘。
节点编号为0到n - 1 。
返回该图中连接的组件的总数。

示例1：
Input: n=5, edges=[[0,1], [1,2], [3,4]]
Output: 2

解题1：

这里我们有两个变量，par和rank。这里par(parent)是用来标记祖先节点的。这里0节点和1节点之间存在边，0位置的rank首先会+1。1和2之间又存在边，实际上2就是0的子孙，因此0位置的rank会再+1。

class Solution:def countComponents(self, n: int, edges: List[List[int]]) -> int:par = [i for i in range(n)]rank = [1] * n# 查找每个节点的顶级父节点def find(n1):res = n1while res != par[res]:# 如果存在连接，就把它连到最高级的父节点上par[res] = par[par[res]]res = par[res]return resdef union(n1, n2):p1, p2 = find(n1), find(n2)if p1 == p2:return 0if rank[p2] > rank[p1]:par[p1] = p2rank[p2] += rank[p1]else:par[p2] = p1rank[p1] += rank[p2]return 1res = nfor n1, n2 in edges:res -= union(n1, n2)return res

时间复杂度: $O(V+E)$
空间复杂度: $O(V+E)$
V 是顶点数，E 是边的数量。