Where is the bug for my code? Please help.


  • 0
    S

    Hi, submission details show 29 / 32 test cases passed.
    I use DFS to check if there is a loop.
    Very basic DFS idea.
    vector<int> st here is a stack.

        class Solution {
        private:
        	bool DFS(const vector<unordered_set<int>> &matrix, const int &n, 
        		const int &numCourses, vector<bool> &flag) {
        
            	vector<bool> visit(numCourses, false);
        
        		visit[n] = true;
        		vector<int> st;
        		st.push_back(n);
        
    // push all the elements into the stack one by one
        		while (!st.empty()) {
        			int top = st.back();
        			flag[top] = true;
                             
    //if all the neighbors are visited && no neighbor is in stack, pop it.
    //if all the neighbors are visited && at least one neighbor is in stack, loop, return false.
        			bool allvisit = true;
        
        			for (auto it = matrix[top].begin(); it != matrix[top].end(); ++it) {
        				if (visit[*it] == false) {
        					visit[*it] = true;
        					allvisit = false;
        					st.push_back(*it);
        				}
        				else if (find(st.begin(), st.end(), *it) != st.end()) {
        					return false;
        				}
        			}
        			if (allvisit == true)
        				st.pop_back();
        		}
        		return true;
        	}
        
        public:
        	bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        		vector<unordered_set<int>> matrix(numCourses);
        		for (int i = 0; i < prerequisites.size(); ++i) {
        			matrix[prerequisites[i][1]].insert(prerequisites[i][0]);
        		}
        
        		vector<bool> flag(numCourses, false);
    // check all nodes one by one    
        		for (int i = 0; i < numCourses; ++i) {
        			if (!flag[i]) {
        				if (DFS(matrix, i, numCourses, flag) == false)
        					return false;
        			}
        		}
        		return true;
        	}
        };

  • 0
    L

    It is kind of difficult to bug other one's code if there is no comment and no input example and error output example.


  • 0
    S

    hi, i add the comments.... please let me know if you could resolve it. thank you.


Log in to reply
 

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