HELP: my c++ solution based on DFS which can only pass 33/34 case


  • 0
    Z

    My solution is based on DFS, when it discovered a vertex which has already been in the stack, in will change the variable 'circle' to false, which means it has circle. But it can only pass 33/34 case, I don't know where I made a mistake.

    WHO CAN HELP ME, I AM GOING TO BE MAD!!!

    Thank you very much

    class Solution {
    public:

    bool canFinish(int numCourses, vector<pair<int, int> >& prerequisites) {
        multimap<int, int> G; // Use Hash map to store the graph.
        bool circle = true;
        
        for (size_t i = 0; i < prerequisites.size(); i++) {
            G.insert(prerequisites[i]); // store the graph using hash multi_map
        }
        
        int* visited = new int[numCourses];
        memset (visited, 0, numCourses * sizeof(visited[0])); // visited[i] = 0 represents vertex i has not been discovered 
        
        for ( int i = 0; i < numCourses; i++ ) {
            if ( visited[i] == 0 ) {
                DFS( G, i, visited, circle );
            }
        }
        
        return circle;
    }
    
    bool hasPathTo(multimap<int, int>& G, int v) {
        int entries = G.count(v);
        if (entries > 0) {
            return true;
        }
        
        return false;
    }
    
    vector<int> pathTo(multimap<int, int>& G, int v) {
        int entries = G.count(v);
        multimap<int, int>::iterator iter = G.find(v);
        vector<int> next;
        
        while (entries--) {
            next.push_back(iter->second);
        }
        
        return next;
    }
    
    void DFS(multimap<int, int>& G, int v, int* visited, bool& circle) {
        visited[v] = 1; // visited[v] = 1 represents vertex v is in stack; which is equal with gray color in Intro to Alf
    
        vector<int> next = pathTo(G, v);
        for (size_t i = 0; i < next.size(); i++) {
            if (visited[next[i]] == 0) {
                visited[next[i]] = 1;
                DFS(G, next[i], visited, circle);
            } else if (visited[next[i]] == 1){
                circle = false;
                return;
            }
        }
    
    	visited[v] = 2; // visited[v] = 2 represents vertex v has been popped out of stack, which is black in Introduction of Algorithm
    
    }
    

    };


  • 0
    A

    How do you know the number of test cases and how many yours passed?


  • 0
    Z

    you can find it after you submit your answer.

    Actually, I didn't add edges to the graph successfully, Now, I have pass the examination


Log in to reply
 

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