C++ 12-13ms DFS using colored vertex


  • 0
    I
    class Solution {
    public:
        struct vertex{
            int val;
            int color;
            // white = 0, means not visited.  gray = 1, means visited. black = 2, means visited and explored
            vector<int> adj;
            vertex(int i) : val(i), color(0){}
            vertex(): val(0), color(0){}
            void update_val(int i){
                val = i; }
            void update_color(int i){
                color = i; }
            void update_adj(int i){
                adj.push_back(i); }
        };
        bool innerCycle(vector<vertex>& vertex_list, int v){
            vector<int> dup_adj = vertex_list[v].adj;
            vertex_list[v].update_color(1);
            for(int i = 0; i<dup_adj.size(); i++){
                if(vertex_list[dup_adj[i]].color == 0){
                    bool sub = innerCycle(vertex_list, dup_adj[i]);
                    if(sub) return true;
                }
                else if(vertex_list[dup_adj[i]].color == 1)
                    return true;
            }
            vertex_list[v].update_color(2);
            return false;
        }
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            if(prerequisites.size() == 0) return true;
            vector<vertex> vertex_list(numCourses);
            for(int i = 0; i< prerequisites.size(); i++){
                vertex_list[prerequisites[i].first].update_adj(prerequisites[i].second);
                vertex_list[prerequisites[i].first].update_val(prerequisites[i].first);
                vertex_list[prerequisites[i].second].update_val(prerequisites[i].second);
            }
    //only insert doubtable vertex into graph. Some courses may be independent to others, so these courses can be ignored while checking the schedule can be finished. 
            for(int i = 0; i< vertex_list.size(); i++){
                if(vertex_list[i].color != 2){
                    bool inner = innerCycle(vertex_list, vertex_list[i].val);
                    if(inner) return false;
                }
            }
            return true;
        }
    };
    

Log in to reply
 

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