Topological Sort

canFinish.cpp

// BFS
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses, vector<int>());
    vector<int> in(numCourses);
    for (auto a : prerequisites) {
        graph[a[0]].push_back(a[1]);
        ++in[a[1]];
    }
    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
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses, vector<int>());
    vector<int> visit(numCourses);
    for (auto a : prerequisites) {
        graph[a[0]].push_back(a[1]);
    }
    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;
}