210. Course Schedule II

    func findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
        var res = [Int]()
        var indegree = [Int: Int]()
        //init indegree
        for i in 0 ..< numCourses {
            indegree[i] = 0
        }
        //get adjacency list
        var adjList = [Int: [Int]]() // from count : to course list
        for pair in prerequisites{
            let next = pair[0]
            let first = pair[1]
            adjList[first, default : [Int]()].append(next)
            indegree[next] = indegree[next]! + 1
        }

        //get indegree == 0
        var queue = [Int]()
        for (course, ind) in indegree{
            if ind == 0 {
                queue.append(course)
                // indegree[course] = nil
            }
        }

        while queue.count > 0 {
            let curr = queue.removeFirst()
            res.append(curr)
            //visit cur
            if let list = adjList[curr]{
                for next in list{
                    indegree[next] = indegree[next]! - 1
                    if indegree[next] == 0 {
                        // indegree[next] = nil
                        queue.append(next)
                    }
                }
            }
        }
        var circles = [[Int]]()
        for (course, ind) in indegree{
            if ind != 0 {
                var currList = [Int]()
                getCircle( course, adjList, &currList, &circles)
                break   //only find one circle
            }
        }
        if res.count != numCourses {
            print(circles)
            return []
        }
        return res
    }



    func getCircle(_ course : Int, _ adj : [Int : [Int]], _ currList: inout [Int], _ res: inout [[Int]]){
        if currList.contains(course) {
            res.append(currList)
            return
        }
        currList.append(course)
        if let list = adj[course] {
            for next in list{
                getCircle( next, adj, &currList, &res)
            }
        }
        currList.removeLast()
    }



    let prerequisites = [[0,1],[1,2],[2,3],[3,1]]
    let number = 4

    findOrder(number, prerequisites)