Leetcode.207.Course Schedule

题目

给一个数n是课程号，需要完成0到n-1的课程。
给定一个二维数组，分别是课程和需求先完成的课程，可能有课程冲突[0,1],[1,0]。
判断是否可以完成所有课程。

Input：2, [[1,0]]
Output：true
Input：2, [[1,0], [0,1]]
Output：false

思路1

DFS。
正向思考，完成课程1需要完成课程2，依次类推，最后判断1是否可以完成。
比较复杂， 时间复杂度较高。

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<int> m_vec(numCourses,1); //0表示未完成课程
    unordered_map<int,unordered_set<int>> m_map; //前置课程
    for (vector<int> vec : prerequisites) {
        if (m_vec[vec[0]] == 1) {
            m_vec[vec[0]] = 0;
        }
        if (m_map.count(vec[0]) == 0) {
            unordered_set<int> set;
            set.insert(vec[1]);
            m_map[vec[0]] = set;
        } else {
            m_map[vec[0]].insert(vec[1]);
        }
    }

    stack<int> m_stack;
    unordered_set<int> m_stackSet;
    for (int i = 0;i < m_vec.size();i++) {
        if (m_vec[i] == 1) {
            continue;
        }
        m_stack.push(i);
        m_stackSet.insert(i);
        while (!m_stack.empty()) {
            int top = m_stack.top();

            if (m_map.count(top) > 0) {
                unordered_set<int> ss = m_map[top];
                unordered_set<int>::iterator iter = ss.begin();
                while (iter != ss.end()) {
                    int x = *iter;
                    if (m_vec[x] == 0) {
                        if (m_stackSet.count(x) > 0) {
                            return false;
                        }
                        m_stack.push(x);
                        m_stackSet.insert(x);
                    }
                    iter++;
                }
            }
            if (top == m_stack.top()) {
                break;
            }
        }

        while(!m_stack.empty()) {
            m_vec[m_stack.top()] = 1;
            m_stackSet.erase(m_stack.top());
            m_stack.pop();
        }
    }

    return true;
}

思路2

BFS。
逆向思维。先找出没有前置课程的课程，以此为突破口，BFS，最后判断最后可以完成的课程和课程总是进行比较。

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    int doneCourse = 0;
    unordered_map<int,vector<int>> m_map;
    vector<int> m_vec(numCourses,0);
    for (vector<int> vec : prerequisites) {
        m_map[vec[1]].push_back(vec[0]);
        m_vec[vec[0]]++;
    }

    queue<int> q;
    for (int i = 0; i < numCourses;i++) {
        if (m_vec[i] == 0) {
            q.push(i);
            doneCourse++;
        }
    }

    while (!q.empty()) {
        if (doneCourse == numCourses) return true;
        int top = q.front();
        q.pop();
        vector<int> preCourses = m_map[top];

        for (int preCourse : preCourses) {
            m_vec[preCourse]--;
            if (m_vec[preCourse] == 0) {
                q.push(preCourse);
                doneCourse++;
            }
        }
    }

    return false;
}

总结

灵活运用逆向思维。熟练掌握BFS和DFS。