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 cycle
        output = []
        visit, cycle = set(), set()
        def dfs(crs):
            if crs in cycle:
                return False
            if crs in visit:
                return True
            
            cycle.add(crs)
            for pre in prereq[crs]:
                if dfs(pre) == False:
                    return False
            cycle.remove(crs)
            visit.add(crs)
            output.append(crs)
            return True

        for 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 True
        
        adj = {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 False

            visit.add(i)
            for j in adj[i]:
                if j == prev:
                    continue
                if not dfs(j, i):
                    return False
            return True
        return 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 = n1

            while res != par[res]:
                # 如果存在连接，就把它连到最高级的父节点上
                par[res] = par[par[res]]
                res = par[res]
            return res

        def union(n1, n2):
            p1, p2 = find(n1), find(n2)
            if p1 == p2:
                return 0
            if rank[p2] > rank[p1]:
                par[p1] = p2
                rank[p2] += rank[p1]
            else:
                par[p2] = p1
                rank[p1] += rank[p2]
            return 1
        
        res = n
        for n1, n2 in edges:
            res -= union(n1, n2)
        return res

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