Graph using bitmap


  • 0
    J
    #define set(map,x) \
    	((map)[(x) >> 5] |= (1 << ((x) & 0x1F)))
    
    #define test(map,x) \
    	((map)[(x) >> 5] & (1 << ((x) & 0x1F)))
    
    
    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{
    			if (courses[i] == 1) // circle
    				return true;
    			if (hasCircle(g, courses, numCourses, i))
    				return true;
    		}
    	}
    	courses[curr] = -1; // all curr's children has been visited
    	return false;
    }
    
    bool canFinish(int n, int** pre, int preRow, int preCol) {
    	if (n <0 || preRow <0  || preCol<0) return 0;
    	if (n == 0) return 0;
    	if (n >= 1 && preRow == 0 && preCol == 0) return 1;
    	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);
    		memset(g[i],0,sizeof(int) * gcol);
    	}
    
    	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);
    	memset(courses,0,sizeof(int) * n);
    
    	int curr;
    	for(int i = 0; i < n; ++i){
    	    if(courses[i] == 0)
    	        if(hasCircle(g, courses, n, i))
    	            return false;
    	}
    
    	return true;
    }

Log in to reply
 

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