c++


  • 0
    U
    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            if (numCourses > 0 && prerequisites.size() > 0) {
                vector<unordered_set<int>> graph;
                stack<pair<int, bool>> trav;
                map<int, bool> dirty;
                bool visited[numCourses];
                for (int i = 0 ; i < numCourses; ++i) {
                    visited[i] = false;
                    unordered_set<int> s;
                    graph.push_back(s);
                }
                for (int i = 0 ; i < prerequisites.size(); ++i) {
                    graph[prerequisites[i].first].insert(prerequisites[i].second);
                }
                for (int i = 0 ; i < numCourses; ++i) {
                    if (!visited[i]) {
                        trav.push(make_pair(i, true));
                        visited[i] = true;
                        while(!trav.empty()) {
                            pair<int,bool> tp = trav.top();
                            dirty[tp.first] = true;
                            trav.pop();
                            if (tp.second) {     
                                trav.push(make_pair(tp.first, false));
                                for (auto idx : graph[tp.first]) {
                                    if (dirty[idx]) {
                                        return false;
                                    }
                                    if (!visited[idx]) {
                                        trav.push(make_pair(idx, true));
                                        visited[idx] = true;
                                    }
                                }
                            } else {
                                dirty[tp.first] = false;
                            }
                        }
                    }
                }
            }
            return true;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.