Leetcode.210.Course Schedule II

题目

给一个数n是课程号，需要完成0到n-1的课程。
给定一个二维数组，分别是课程和需求先完成的课程，可能有课程冲突[0,1],[1,0]。
输出上课顺序，如果有冲突返回空。

Input：2, [[1,0]]
Output：[0,1]
Input：4, [[1,0],[2,0],[3,1],[3,2]]
Output：[0,1,2,3] or [0,2,1,3]

思路

BFS。

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    unordered_map<int,vector<int>> m_map;
    vector<int> m_vec(numCourses,0);
    int doneCourse = 0;
    for (vector<int> vec : prerequisites) {
        m_map[vec[1]].push_back(vec[0]);
        m_vec[vec[0]]++;
    }
    queue<int> q;
    vector<int> res;
    for (int i = 0; i < numCourses; i++) {
        if (m_vec[i] == 0) {
            q.push(i);
            res.push_back(i);
            doneCourse++;
        }
    }
    while (!q.empty()) {
        if (doneCourse == numCourses) {
            return res;
        }
        int top = q.front();
        q.pop();
        vector<int> courses = m_map[top];
        for (int course : courses) {
            m_vec[course]--;
            if (m_vec[course] == 0) {
                doneCourse++;
                q.push(course);
                res.push_back(course);
            }
        }
    }

    return vector<int>();
}

总结

熟练使用BFS和DFS。