题目

course-schedule

算法

* BFS

* DFS

代码

* BFS

class Solution {

public:

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {

        vector<vector<int> > graph(numCourses, vector<int>(0));

        vector<int> in(numCourses, 0);

        for (auto a : prerequisites) {

            graph[a[1]].push_back(a[0]);

            ++in[a[0]];

        }

        queue<int> q;

        for (int i = 0; i < numCourses; ++i) {

            if (in[i] == 0) q.push(i);

        }

        while (!q.empty()) {

            int t = q.front();

            q.pop();

            for (auto a : graph[t]) {

                --in[a];

                if (in[a] == 0) q.push(a);

            }

        }

        for (int i = 0; i < numCourses; ++i) {

            if (in[i] != 0) return false;

        }

        return true;

    }

};

* DFS

class Solution {

public:

    bool canFinish(int numCourses, vector<vector<int> >& prerequisites) {

        vector<vector<int> > graph(numCourses, vector<int>(0));

        vector<int> visit(numCourses, 0);

        for (auto a : prerequisites) {

            graph[a[1]].push_back(a[0]);

        }

        for (int i = 0; i < numCourses; ++i) {

            if (!canFinishDFS(graph, visit, i)) return false;

        }

        return true;

    }

    bool canFinishDFS(vector<vector<int> > &graph, vector<int> &visit, int i) {

        if (visit[i] == -1) return false;

        if (visit[i] == 1) return true;

        visit[i] = -1;

        for (auto a : graph[i]) {

            if (!canFinishDFS(graph, visit, a)) return false;

        }

        visit[i] = 1;

        return true;

    }

};