剑指 Offer II 113. 课程顺序

拓扑排序 bfs

func findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
        
        //开始构造图 edges 存储对应节点相邻的节点
        var edges = [[Int]](repeating: [], count: numCourses)
        //存储对应节点的入度
        var indeg = Array.init(repeating: 0, count: numCourses)
        for info in prerequisites {
            edges[info[1]].append(info[0])
            indeg[info[0]] += 1
        }
        var tempArray = [Int]()
        for i in 0..<numCourses {
            //查找入度为0的节点加入队列
            if indeg[i] == 0 {
                tempArray.append(i)
            }
        }
        
        var res = [Int]()
        while !tempArray.isEmpty {
            
            let v = tempArray.removeLast()
            res.append(v)
            for nextV in edges[v] {
                //因为节点被移除 那么相邻节点的入度减少1
                indeg[nextV] -= 1
                if indeg[nextV] == 0 {
                    tempArray.insert(nextV, at:0)
                }
            }
            
        }
        
        if res.count == numCourses {
            return res
        }
        return []
        
    }

dfs

func findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
        
        //开始构造图
        var edges :Array<Array<Int>> = Array.init(repeating: [], count: numCourses)
        var visited = Array.init(repeating: 0, count: numCourses)
        var hasCircle = false
        for info in prerequisites {
            edges[info[1]].append(info[0])
        }
        var res = [Int]()
        for i in 0..<numCourses {
            //如果节点没有搜索过
            if visited[i] == 0{
                dfs(i,edges,&visited,&res,&hasCircle)
                if hasCircle {
                    return []
                }
            }
            
        }
        
        if res.count == numCourses {
           return res
        }
        
        return []
        
        
        
    }
    
    func dfs(_ v:Int,_ edges:[[Int]], _ visited: inout [Int],_ res: inout [Int],_ hasCircle: inout Bool){
    
        //标记为搜索中
        visited[v] = 1
        
        for nextV in edges[v] {
            //未搜索过
            if visited[nextV] == 0 {
                dfs(nextV,edges,&visited,&res,&hasCircle)
                if hasCircle {
                    return
                }
            }else if visited[nextV] == 1{
                hasCircle = true
                return
            }
            
        }
        visited[v] = 2
        res.insert(v, at: 0)

    }