[Courses Schedule] what's wrong with my code?


  • 0
    J
    	#define set(map,x) \
    	(map[x >> 5] |= (1 << (x & 0x1F)))
    
    #define test(map,x) \
    	(map[x >> 5] & (1 << (x & 0x1F)))
    
    int getUnvisited(int *courses, int numCourses){
    	static int unvisited = 0;
    	while (unvisited < numCourses && courses[unvisited] != 0)
    		unvisited++;
    
    	return unvisited;
    }
    
    bool hasCircle(int **g, int *courses, int numCourses, int curr){
    	// courses[curr] is been visiting by children , set it = 1
    	courses[curr] = 1;
    	for (int i = 0; i < numCourses; ++i){
    		if (!test(g[curr], i)) continue;
    		else{
    			// i prerequise curr
    			if (courses[i] == 1) // circle
    				return true;
    			if (hasCircle(g, courses, numCourses, i))
    				return true;
    		}
    	}
    	courses[curr] = -1;
    	return false;
    }
    
    bool canFinish(int n, int** pre, int preRow, int preCol) {
    	if (preRow <= 1) return true;
    	int **g = malloc(sizeof(int *)* n);
    	int gcol = (n + 31) / 32;
    	int grow = n;
    	for (int i = 0; i < grow; ++i){
    		g[i] = malloc(sizeof(int)* gcol);
    		for (int j = 0; j < gcol; ++j)
    			g[i][j] = 0;
    	}
    
    
    	/// g[i][j] stands for course j prerequires course i
    	for (int i = 0; i < preRow; ++i){
    		int a = pre[i][0];
    		int b = pre[i][1];
    		set(g[a], b);
    	}
    	
    
    	// graph complete
    
    	// dfs to detects circle
    
    	int *courses = malloc(sizeof(int)* n);
    	for (int i = 0; i < n; ++i)
    		courses[i] = 0;
    
    	int curr;
    	while ((curr = getUnvisited(courses, n)) != n){
    		if (hasCircle(g, courses, n, curr))
    			return false;
    	}
    	return true;
    }

  • 1
    J

    Well, the "bug" is not your code, it's the OJ!

    You should not use the "static" keyword here because it will not reset to 0 in each execution of the canFinish function. Basically, in test case one, your answer will be correct, but in test case two, you probably will get a wrong answer because your "unvisited" variable is not 0 anymore.

    This is a very common but bad way of implementing an OJ, because it doesn't separate each test. And this is also the reason why a "Time Limit Exceeded" will screw all.

    So just delete the "static unvisited = 1", make "unvisited" a real global var, and assign it to 0 in canFinish function. Also pay attention to the line "int curr;", you should make it "int curr = 0", it's safer.

    Another advise is for your DFS.
    Your base case handling is a little wired. Although you can get THIS problem AC, your dfs’s base case here is buggy.
    You should not do “courses[curr] = 1”, instead, you should firstly check “if(courses[curr] == -1)”, otherwise, you will
    revisit a node and your DFS tree is not correct!


  • 0
    J

    thank you very much!


Log in to reply
 

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